Tài liệu Cân bằng tải tối ưu trong mạng truyền dữ liệu

ĐẠI HỌC QUOC GIA HA NỘI KHOA CỒNG NGHỆ NGUYỄN HỒNG HẠNH CÂN BẰNG TẢI TỐI ƯU TRONG MẠNG TRUYỀN DỮ LIỆU ■ ■ Chuyên ngành: K ỹ thuật vô tuyến điện tử và thônq tin liên lạc Mã số: 0 2 .0 7 .0 0 LUẬN VĂN THẠC SỸ ■ ■ NGƯỜI H UỚNG D Ẫ N K H O A HOC TS. T R Ầ N H Ổ N G Q U Â N GAI H O C Q U Ố C G iA HA NỘI TRŨNGTÁM THGHGTW THU V íu ’ Z \ z iũịổU.O Hà nội - 2003 MỤC LỤC Trang Mục lục Danh mục các tù viết tắt MỞ ĐẦU CHƯƠNG 1: CÂU TRÚC M ẠNG 1 CHƯƠNG 2: CẢN BANG TẢI TRONG CÂU HÌNH MẠNG SAO ĐƠN KÊNH ............................................................................................................................... 5 2.1 Giới thiệu ........................................................................................................ 5 2.2 Cân bằng tải trong môi trường đơn lớp 6 2 .2 .1 Giới thiệu...................................................................................................... 6 2.2.2 Mô h ìn h ...................................................................................................... 7 2.2.3 Cân bằng tái tối ưu.................................................................................... 9 2.2.4 So sánh đặc tính thuật toán cân bằng tả i............................................. 14 2.2.5 Thuật toán cho m ạng hình sao ................................................................ 15 2.2.6 Kết lu ận .................................................................................................................... 16 2.3 Cân bằng tải tối ưu trong môi trường đa lớp 16 2.3.1 Giới thiệu...................................................................................................... 16 2.3.2 M ô tả m ô h ìn h ............................................................................................. 17 2.3.3 N ghiệm tối ưu.............................................................................................. 20 2.3.4 Thuật toán cân hằng tải tối ư u ................................................................ 25 2.3.5 So sánh tốc độ các thuật to á n ................................................................. 32 2.3.6 Kết lu ận ......................................................................................................... 37 CHƯƠNG 3: CÂN BANG TẢI TỐI ƯU CHO TOÀN BÔ TẢI Đ ố i VỚI TẢI TỐI ƯU RIÊNG LẺ 3.1 Giới thiệu 3.2 Cân bàng tải tĩnh trong 38 mạng đơn kênh 39 3.2.1 M ô tả m ô hình 40 3.2.2 N ghiệm tôi ưu............................................................................................. 42 3.2.3 Phân tích tham s ố ..................................................................................... 44 3.2.4 Tác động bất thường của sự tối ưu và sự cân b ằ n g ......................... 52 3.2.5 Tính toán bằng s ố ....................................................................................... 53 3.2.6 Kết lu ậ n ......................................................................................................... 56 3.3 Cân bằng tải tĩnh trong mạng hình sao 58 3.3.1 Mô tả m ô hìn h ............................................................................................ 58 3.3.2 Nghiệm tối ưu............................................................................................. 59 3.3.3 Phân tích tham số ....................................................................................... 65 3.3.4 Tác động bất thường của các biến tối ưu.......................................... 71 3.3.5 Tính toán bằng s ố ...................................................................................... 73 3.3.6 Thảo luận..................................................................................................... 76 3.4 Cân bàng tái tĩnh trong môi trường đơn kênh đa lớp 78 3.4.1 Mô hình 78 3.4.2 Tính toán bằng s ố ...................................................................................... 83 3.4.3 Thảo lu ận ..................................................................................................... 88 3.4.4 Kết luận..................................................................................................... 89 KẾT LUẬN TÀI LIỆU THAM KHẢO DANH MỤC TỪ VIẾT TẮT [CPU] : Central Processing Unit [I/O ] : Input/Output [FD] : Flow deviation [FCFS]: First come first served MỎ ĐẦU Công nghệ mạng truyền dữ liệu đã có những bước phát triển đáng kể trong những năm gần đây. Nhờ vào đó các mạng truyền dữ liệu đã có các tính năng mới hỗ trợ việc truyền các ứng dụng thương mại rộng lớn cũng như các ứng dụng đặc biệt quan trọng khác như các giao dịch tài chính, truy nhập cơ sở dữ liệu, Web, dòng dữ liệu âm thanh, hình ảnh, .... Các ứng dụng này có tần suất sử dụng cao, (hỏng thường phái chạy liên tục 24 giờ trong ngày, 7 ngày trong 1 tuần. Do vậy, hệ thống mạng phái có khả năng mở rộng tối ưu để có thể đáp ứng được số lượng lớn các yêu cầu của người sử dụng mà không gây ra bất kỳ một độ trễ không mong muốn nào Một trong những xu hướng gần đây về hệ thống mạng là phân tán sự tính toán giữa các bộ xử lý vật lý. Các bộ xử lý trong hệ thống mạng phân tán có thê khác nhau về quy mô và chức năng. Chúng thường bao gồm các bộ vi xử lý nhỏ, các máy trạm, các máy tính mini và hệ thống máy tính đa năng lớn. Các bộ xử lý này thường được gọi là các node. Sự nghiên cứu vể hệ thống mạng phân tán bao gồm nhiéu lĩnh vực như: mạng truyền thông, hệ điều hành phân tán, cơ sở dữ liệu phân tán, ngôn ngữ lập trình chung và phân tán, lý thuyết về các thuật toán song song và phân tán, cấu trúc nối mạng, độ tin cậy và khả năng lỗi, hệ thống phân tán trong thời gian thực, khả năng gỡ lỗi phân tán và các ứng dụng phân tán [13]. Như vậy, hệ thông mạng phân tán bao gồm mạng vật lý, các node và tất cả các phần mềm điều khiển. Có 5 lý do để xây dựng một hệ thống mạng phân tán, đó là: chia sẻ tài nguyên, cải tiến sự tối ưu, độ tin cậy, khả nâng truyền thông và độ khả mở. Một trong những vấn đề thú vị nhất của hệ thống mạng phân tán là cải tiến sự tối ưu của hệ thống thông qua sự cân bằng tải giữa các node [12]. Với lý do trên, tôi đã lựa chọn đề tài luận văn tốt nghiệp là nghiên cứu về cân bằng tái tối ưu trong mạng truyền dữ liệu. Đó là một vấn đề quan trọng trong việc phát triển công nghệ mạng. Các kết quả nghiên cứu về cân bằng tải có thê được sử dụng hữu ích trong việc thiết kế hệ thống mạng phán tán hay điều chinh các tham số hợp lý để nâng cao sự tối ưu của hệ thống. Trong luận văn này, tôi tập trung nghiên cứu về cân bằng tải trong cấu hình mạng đơn kênh (mạng bus), trong cấu hình mạng sao đơn kênh, dưa ra các thuật toán cân bằng tải cho môi trường đơn lớp và đa lớp cho các cáu hình mạng nói trên và so sánh đặc tính các thuật toán càn bằng tải. Ngoài ra, luận văn còn nghiên cứu về hai phương pháp cân bằng tải là cân bằng tải tối ưu cho toàn bộ tải và cân bằng tải tối ưu cho các tải riêng lẻ thông qua sự phân tích tham số. Cấu trúc của luận văn gồm các phần sau: Mở đầu Chương 1: Trình bày về cấu trúc mạng Chương 2: Trình bày về cân bằng tải trong cấu hình mạng sao đơn kênh Chương 3: Trình bày về cân bằng tải tối ưu cho toàn bộ tải đối với tải tối ưu riêng lẻ. Kết luận Nội dun° nghiên cứu luận văn này được xây dựng trên cơ sở những kiến thức đã được tiếp thu trong quá trình học tập, nghiên cứu tại khoa Công nghệ, Đại học Quốc gia Hà nội cũng như thời gian công tác tại Trung tâm Tin học. Bưu điện Hà nội. Với thời gian nghiên cứu hạn hẹp, luận văn này không tránh khỏi có những sai sót, tác giả mong được sự góp ý chí bảo của các thầy cô và bạn bè đồng nghiệp. Qua đây, tác giả xin gửi lờicảm ơn chân thành đến TS. Trần Hổng Quân - Viện Khoa học Kỹ thuật Bưu điện đã hướng dẫn tận tình, có nhiều lời góp ý, cùng nhiều tài liệu bố ích đê luận văn này được hoàn thành. Tác giả cũng xin chân thành cảm ơn các thầy cô giáo khoa Công nghệ, Đại học Quốc gia Hà nội đã tạo điều kiện học tập và nghiên cứu cho tác giả trong hai năm học vừa qua. Xin chân thành cảm ơn các bạn bè đồng nghiệp, các bạn học cùng lớp đã có những lời động viên quý báu trong suốt thời gian thực hiện luận văn này. Hà nội, thúng 06 năm 2003 Nguyễn Hồng Hạnh CHƯƠNG 1 : CẨu TRÚC MẠNG Sự kết hợp của máy tính với các hệ thống truyền thông (communication) đặc hiệt là viễn thông (telecommunication) đã tạo ra một sự chuyến biến có tính chất cách mạng trong vấn đề tổ chức khai thác và sử dụng các hệ thống máy tính. Mô hình tập trung dựa trên các máy tính lớn với phương thức khai thác theo “lô” đã được thay thê bởi một mô hình tổ chức sử dụng mới, trong đó các máy tính đơn lẻ được kết nối lại để cùng thực hiện công việc. Một môi trường làm việc nhiều người su dụng phân tán đã hình thành cho phép nâng cao hiệu quả khai thác tài nguyên chung từ những vị trí địa lý khác nhau. Các hệ thống như thế được gọi là các mạng máy tính. Trong những năm 70 của thế kỷ 20. bắt đầu xuất hiện khái niệm Mạng truyển thông (communication network), trong đó các thành phần chính của nó là các nút mạng, được gọi là các bộ chuyển mạch dùng đê hướng thông tin tới đích của nó. Các nút mạng được nối với nhau bằng đường Iruyền còn các máy tính xử lý thông lin qua trạm Host hoặc các trạm cuối được nối trực tiếp vào các nút mạng để khi cần thi trao đối thông tin qua mạng. Bán thân các nút mạng thường cũng là máy tính nên có thể đổng thời đóng cả vai trò máy của người sử dụng [ 1]. Với nhận xét này, trong phạm vi của luận văn, chúng tôi không phân biệt khái niệm mạng máy tính và mạng truyền thông. Các máy tính được kết nối thành mạng máy tính nhằm đạt tới các mục tiêu chính sau đây: Làm cho các tài nguyên có giá trị cao (thiết bị, chương trình, dữ liệu...) trở nên khả dụng đối với bất kỳ người sử dụng nào trên mạng (không cần quan tàm đến vị trí địa lý của tài nguyên và người sử dụng). - Tăng độ tin cậy của hệ thống nhờ khả năng thay thế khi xáy ra sự cố đối với một máy tính nào đó (rất quan trọng đối với các ứng dụng thời gian thực). Kiến trúc mạng niáv tính Kiến trúc mạng máy tính thể hiện cách nối các máy tính với nhau ra sao và tập hợp các quy tắc. qui ước mà tất cả các thực thê tham gia truyền thông trên mạng phải tuân theo đế đám báo cho mạng hoạt động tốt. Sự sắp xếp vật lý đặc trung của các thành phần của mạng được gọi là hình trạng (topology) cùa mạng. Còn tập hợp các qui tắc, qui ước truyền thông thì được gọi là giao thức của mạng. Tdpoloụy mang Hai mạng có cùng một hình trạng nếu cấu hình nối mạng là như nhau, mặc dù hai mạng này khác nhau trong kết nối vật lý, khoảng cách giữa các node, vận tốc truyền hoặc loại tín hiệu. Các dạng hình trạng mạng phố biến hiện nay như sau [8]: * Mạng bus: là hình trạng mạng mà ở đó tất cả các node (các trạm) được nối với nhau bởi 1 đường bus đơn. ■ Mạng nối đầy đu: là hình trạng mạng mà ở đó tồn tại một đường nối trực tiếp (nhánh) giữa hai node. Nếu một mạng nối đầy đù có n node thì có n(n-l) nhánh trực liếp. ■ Mạng lai: là sự kết hợp của hai hoặc nhiều hình trạng mạng ■ Mạng hình lưới: là hình trạng mạng mà ở đó có ít nhất 2 node có 2 đường hoặc nhiều hơn 2 đường nối giữa chúng. ■ Mạng mạch vòng: là hình trạng mạng mà ở đó mỗi node có 2 nhánh nối tới nó. ■ Mạng hình sao: là hình trạng mạng mà ở đó mỗi node ngoại vi được nối với node trung tâm, node trung tâm này quảng bá lại tất cả các tín hiệu mà nó nhận dược từ một node ngoại vi nào đó tới tất cả các node ngoại vi còn lại, kể cả node gửi tín hiệu ban đầu . Tất cả các node ngoại vi giao tiếp với các node còn lại chỉ bằng cách gửi đến hoặc nhận từ node trung tâm. ■ Mạng hình cây: là hình trạng mạng mà ở đó, từ một cách nhìn hoàn toàn hình thái, tương tự như một sự kết nối giữa các mạng hình sao, sao cho mỗi node ngoại vi riêng lẻ chỉ được nhận hoặc truyền từ một node khác hướng về node trung tâm và được yêu cầu không hoạt động như một bộ nhắc lại. Có 2 kiểu nối mạng chủ yếu là điểm - điểm và quáng bá (broadcast hay point to multipoint) Theo kiểu điểm - điểm, các đường truyền nối từng cặp nút với nhau và mỗi nút đều có trách nhiệm lưu giữ tạm thời sau đó chuyển tiếp dữ liệu đi cho tới đích. Do cách thức làm việc như thế nên mạng kiểu này còn được gọi là mạng lun và 2 thoát. Một số dạng của mạng điểm - điểm là mạng hình sao, hình cây, mạng kết nối đầy đủ, ... được trình bày tại hình 1.1 * : t : M ạng hình sao M ạng kết nối đầy đủ • Node Nhánh M ạng hình cây M ạng hình lưới Hình 1.1 Theo kiểu quảng bá, tất cả các nút phân chia chung một đường truyền vật lý. Dữ liệu được gửi đi từ một nút nào đó sẽ có thể được tiếp nhận bởi tất cả các nút còn lại, bởi vậy cần chỉ ra địa chi đích của dữ liệu để mỗi nút căn cứ vào đó kiểm tra xem dữ liệu có phải dành cho minh hay không? Một số ví dụ của mạng kiểu quảng bá là mạng vòng, mạng b u s ,... được trình bày tại hình 1.2 M ạng bus M ạng mạch vòng kép • M ạng mạch vòng Node Nhánh Hình 1.2 3 Trong các topology dạng bus và vòng cần có một cơ chế “trọng tài” để giải quyết “xung đột” khi nhiều nút muốn truyền tin cùng một lúc. Việc cấp phát đường truyền có thể là “tĩnh” hoặc “động”. Cấp phát “tĩnh" thường dùng cho cơ chê vòng để phân chia đường truyền theo các khoảng thời gian định trước. Còn cấp phát “động” là cấp phát theo yêu cầu để hạn chế thời gian “chết” vô ích của đường truyền. Giao thức maiiíi Việc trao đổi thông tin, cho dù là đơn giản nhất, cũng đểu phải tuân theo những quy tắc nhất định. Ngay cả hai người nói chuyện với nhau muốn cho cuộc nói chuyện có kết qua thì ít nhất cả hai người cũng phải ngầm tuân thủ quv tắc: khi người này nói thì người kia phải nghe và ngược lại. Việc truyền tín hiệu trên mạng cũng vậy, cần phải có những quy tắc, quv ước về nhiều mặt, từ khuôn dạng của dữ liệu cho tới các thủ tục gửi, nhận dữ liệu kiểm soát hiệu quả và chất lượng truyền tin và xử lý các lỗi và sư cố. Yêu cầu về xử lý và trao đổi thông tin của người sử dụng càng cao thì các quy tắc càng nhiều và càng phức tạp hơn. Tập hợp tất cả những quy tắc, quy ước đó được gọi là giao thức của mạng. Rõ ràng là các mạng có thể sử dụng các giao thức khác nhau tuỳ sự lựa chọn của người thiết kế. 4 CHƯƠNG 2: CÂN BẰNG TẢl TRONG cXu HÌNH MẠNG SAO ĐƠN KÊNH 2.1 GIÓI THIỆU Trong phạm vi chương này chúng ta sẽ nghiên cứu cân băng tải tĩnh trong mạng hình sao đơn kênh. Tantawi và Towsley [14, 15] đã nghiên cứu cân bằng tái trong môi trường đơn lớp của một hệ thống mạng phân tán bao gồm các trạm không đồng nhất được nối bời các kênh đơn trong mạng hình sao. Họ quan tâm tới các thuật toán cân bằng tải tối ưu để xác định tải tối ưu tại mỗi trạm sao cho tối thiếu được thời gian đáp ứng gói tin trung bình. Họ đã tìm được hai thuật toán (được gọi là thuật toán đơn điểm) xác định tải tối ưu tại mỗi trạm với một số thông số hệ thống cho trước. Càn bằng tải tĩnh được dùng trong việc hoạch định quy mỏ của hệ thống (ví dụ xác định vị trí của các tài nguyên, phát hiện nghẽn cổ chai, nghiên cứu độ n hạy,...). Các giải pháp cân bằng tải tối ưu có thể giúp chúng ta thiết kế hệ thống. Đầu tiên, chúng ta quan tâm tới cấu hình hệ thống mạng đơn kênh giống như Tantawi và Towsley đã đề cập tới. Một số đặc tính bổ sung mà giải pháp tối ưu thoả mãn đã được tìm thấy. Trên cơ sở của các đặc tính này, một thuật toán đơn điểm dễ hiểu và đơn giản hơn nhiều so với thuật toán của Tantawi và Towsley đã được giới thiệu. Sự tối ưu của thuật toán này được so sánh với thuật toán của Tantawi và Tovvsley. Số lượng các bước chương trình để thực hiện thuật toán này chi bằng khoảng 1/3 so với thuật toán của Tantawi và Towsley. Trong quá trình tính toán thực nghiệm, thuật toán mới chi yêu cầu 2/3 thời gian tính toán so với thời gian tính toán mà thuật toán Tantawi và Towsley yêu cầu. Đối với mạng hình sao, một thuật toán cân bằng tái hiệu quả hơn so với thuật toán của Tantawi và Towsley đã được đưa ra. Tiếp theo, mỏ hình đơn lớp đã được mở rộng thành môi trường đa lớp của mạng đơn kênh. Một thuật toán hiệu quả về cân bằng tải tối ưu cho môi trường đa lớp cũng được trình bày. Hiệu quả của thuật toán được trình bày ở đây cho môi trường đa lớp dược so sánh với các thuật toán đã biết khác là thuật toán lệch dòng (FD) và thuật toán Dafermos. Cả thuật toán vừa trình bày và thuật toán FD yêu cầu dung lượng nhớ ít hơn nhiều so với thuật toán Dafermos. Trong quá trình tính toán bằng số, thuật toán trình bày ở đây và thuật toán Dafermos yêu cầu thời gian tính toán để tìm nghiệm tối ưu nhỏ hơn nhiều so với thuật toán FD. 2.2 CÂN BẲNG TẢI TRONG MÔI TRƯỜNG ĐƠN LÓP 2.2.1 Giới thiệu Tantawi và Towsley đã tập trung vào thuật toán cân bằng tai tĩnh để xác định tải tối ưu tại mỗi trạm nhằm tối thiểu hoá thời gian đáp ứng trung bình của hệ thống. Họ đã trình bày mô hình của hệ thống máy tính phân tán bao gồm các trạm không đồng nhất được liên kết bởi một mạng dơn kênh. Tính chất quan trọng của chúng là sự trễ của quá trình truyền thông không phụ thuộc vào cặp nguồn - đích. Tính chất này áp dụng cho mạng đơn kênh như mạng vệ tinh và một số mạng LAN. Với các giả thiết này, chúng xác định các yêu cầu mà tải tối ưu tại mỗi trạm phải thoả mãn, dẫn đến thuật toán xác định tải tối ưu tại mồi trạm tương ứng với một sô' thông số hệ thống cho trước. Thuật toán này được gọi là thuật toán đơn điểm. Thuật toán đơn điểm của Tantawi và Towsley đã gây chú ý bởi lẽ nó không tính tải tại từng nốt một cách lặp đi lặp lại. Lưu ý rằng các thuật toán trước đó trên các mỏ hình liên quan như thuật toán dạng chệch dòng (flow deviation) [7J hay thuật toán dạng Gauss-Seidel ị 10] yêu cầu tính toán tải lặp đi lặp lại. Mặt khác, thuật toán này tỏ ra phức tạp và khó hiếu. Trong phần này, chúng ta quan tâm tới mô hình giống như của Tantawi và Towsley dưới cùng tính chất liên quan đến sự trễ của quá trình truyền thông. Ngoài ra, chúns ta cũng chỉ ra một số tính chất mà giải pháp tối ưu thoả mãn. Trên cơ sở của các tính chất này, thuật toán đơn điếm khác đơn giản và dễ hiểu hơn nhiều so với thuật toán Tantawi và Towsley đã được giới thiệu. Hơn nữa, hàng loạt các tính chất liên quan đến sự hội tụ của thuật toán được xác định và sự tối ưu của nó được trình bày. Một thuật toán cân bằng tải cho mạng phân tán hiệu quả hơn thuật toán của Tantawi và Towsley cũng được đề cập đến. 6 2.2.2 Mô hình Trong luận văn này chúng tôi chọn mỏ hình giông như mô hình cùa Tantawi và Towsley. Như vậy, hệ thống được bao gồm n node (trạm) được nối với nhau bởi mạng đơn kênh (Hình 2.1) t p, Tà i n g u y ê n và h à n g đợi ỵ - 1 - Node n Node i X | J r 5 Ị M ạ n g t r u y ề n d ữ liệu Node 1 j j N ode 2 H ì n h 2.1 Hệ t h ố n g m ạ n g p h â n t án Gói tin đến node i, i = 1 ,2 ......N theo quá trình Poisson bất biến theo thời gian. Một gói tin đến node i có thê được xử lý tại node i hoặc dược truyền qua mạng đến node j. Chúng ta giả sử rằng quyết định để truyền một gói tin không phụ thuộc vào trạng thái cua hệ thống vì thế được gọi là tĩnh. Cũng như vậy, chúng ta giá sử rằng gói tin được truyền từ node i sang node j. tại node J nó được nhận các dịch vụ và không truyền sang các node khác. Cũng giả thiết rằng độ trễ của quá trình truyền từ node i tới node j không phụ thuộc cặp nguồn - đích (i,j). // số lượng node p, tần suất xử lý gói tin (tải) tại node i. p [P i,P 2. - P J Xịj tần suất dòng gói tin từ node i tới node j (ị), tần suất gói tin ngoài đến tới node i. 0 tổng tần suất gói tin ngoài (0=Xội) Ằ lưu lượng của mạng. , 7 Fj(Pj) độ trễ node trung bình của gói tin được xử lý ở node i - hàm dương tăng. G(À) độ trễ truyền trung bình không phụ thuộc cặp nguồn - đích - hàm dương không giám. Các loại node dược clịnh nghĩa như sau [2]: (1) nguồn rỗi (Rti) : node không xử lý bất kỳ một gói tin nào, (3=0. (2) Nguồn hoạt động (Ra) : node gửi gói tin và không nhận bất cứ gói tin nào nhưng node xử lý một phần gói tin đến node đó. (3) Trung lập (N): node xử lý gói tin tại chỗ mà không nhận hoặc gửi bất kỳ gói tin nào. (4) Chìm (sink) (S): node nhận gói tin từ các node khác gửi đến mà không gửi bất cứ gói tin nào. Để tối thiếu hoá thời gian đáp ứng trung bình của gói tin phải thoả mãn các điều kiện sau: Tim cực tiểu hàm trễ xử lý: (2. 1) với già thiết /?, >0, i = l,2,...n trong đó lưu lượng của mạng X có thể được biểu diễn hởi các biến (3 như sau: , ( 2.2) Chúng ta nhận thấy tần suất dòng gói tin Xjj trong mạng truyền thông có thể xác định tuỳ ý trong khi điều kiện cân bằng dòns gói tin được thoả mãn. Cụ thể, chúng ta có thể cho rằng tần suất dòne gói tin từ node i tới node j tỷ lệ thuận với sự đóng góp của node J với mức tải của mạng, có nghĩa là: 8 {P' 0, Khi node J ệ,\ệ ,- p ,) , i e R r R, je s, còn lại. là node chìm, số lượng Pj - 4J ( > 0) biểu diễn lưu lượng gửi tới node j. > Mặt khác, node i là nguồn cho nên 4 , - (3, ( > 0) biểu diễn lưu lượng được gửi đi từ > node i. 2.2.3 Can băng tái tôi ưu Định nghĩa 2 hàm số sau: ỡ/?, g(Ẫ) = ~ ( Ả G ( Ả ) ) ÕÀ Hàm nghịch đảo của giới hạn trễ tại node được định nghĩa như sau: A ./» =* ./. (()) > -V 0. Tantawi và Towsley phát biểu các định lý sau bằng cách sử dụng các định lý của Kuhn-Tucker Ị 15]: [Định lý cua Tantawi và Towsley] nghiệm tối ưu của phương trình (2.1) thoá mãn các môi quan hệ: f, ( j 3, ) >a + gỤl),/? j= 0 ( i e R d), f l(j3,) = a + g(Ả), 0 < p t <ệ, a < f , ( p , ) < a + g{Ả), pị=ệ, ( i e R a), (2.3) ( ie N ) , « = /,(A)> Pị>ệ, (ieS), \ (V giá thiết điều kiên của dòng thông tin tổng: i ] T / , “'(a + g ('0) + X<^' ie l< leN = ®(2.4) leS trong đó a là thừa số Lagrange (Lagrange multiplier). Thuật toán đơn điểm của Tantawi và Towsley [ 15] đầu tiên xác định thành phần của từng node. Sau đó giải phương trình (2.4) của a , và thu được giá trị của p,, xác định bởi giá trị a đó. Trong các tình huống thực tê chúng ta hiếm khi thu được công thức sát thực đưa ra a từ phương trình (2.4). Do vậy, chúng ta thường sử dụng phương 9 pháp lãp. Trong khi cân bằng tải thông thường không đòi hỏi độ chính xác cao, một phương pháp đơn giản như tìm kiếm nhị phân được sử dụng bằng cách giải phương trình của a (2.4) bằng phương pháp lặp. Với mục đích phát triển thuật toán này, các tính chất dưới đây thu được trực tiếp từ định lý Tantawi-Towsley. Cho rằng p là nghiệm tối ưu của phương trình (2.1) và cho biết: a = min f ậ(Pệ), (2.5) Ả =\ỵ\,-p\ (2.6) ^ /=l Từ định lý nói trên, rút ra một số trường hợp đặc biệt thoả mãn tại nút J bất kỳ. Trường Í1ƠP I / ( 0 ) > « + g(Ã), nếu /?, = 0 /,(,)> a + g(Ã)> f,(0) a < f ẩ(ật) < a + g(Ả), a >/,(,), nêu 0 < ,, nếu p, >ệ, , Chứng minh: Từ giả thiết ban đầu, lun ý rằng f,(Pi) và g(/.) tương ứng là tăng và không giám, cả 2 hàm đều là dương. Điểu đó rõ ràng từ mối quan hệ biếu diễn ở (2.3) là a - min fj(Pi), điều này cũng giống như phương trình (2.5). Như vậy, cả hai (X đều là một. Chúng ta thấy rằng X được định nghĩa ở (2.6) là lưu lượng mạng trong giai pháp tối ưu. / , ( 0 ) > a + g(A), /3, =0 nếu ./; (< ,)> a + g(Ẳ) > ./; (0) /> a < f l( ệ , ) /; (ộ, ), nếu nếu nếu 0 ệ„ Điều kiện cần trong (2.7): có thể thu được dễ dàng từ những phát biểu ở quan hệ 2.3 Điều kiện đủ ớ (2.7): sự đáo ngược có thể được chi ra bằng mâu thuẫn (ví dụ, giả thiết rằng với vài giá trị của i, p, > 0 khi f,(0) > oc + g(Ằ,). Như vậy từ những điều 10 kiện ở trên, chúng ta thấy rằng với i. a + g(X) > f,(0), điều này mâu thuẫn với giả thiết đặt ra). Lưu V các định nghĩa sau trong giải pháp tối ưu Rj = {iiPi = 0} (nguồn rỗi) Ra = Ị iio < (3, < (ị), Ị (nguồn hoạt động) N = Ịilp, = ộ, í (trung lập) s = {iip, > (Ị),} (chìm) Trườnu hop 2 : nếu [3 là nghiệm tối ưu cho phương trình (2.1) thì chúng ta có: Pi = 0, i e R d, (3, = f, '(a+g(À)) i e R a, Pi = 4 i > ie N , 3, = IV‘ (a) i eS. Chứng minh: Điều này là rõ ràng từ định lý Tantawi-Towsley. Trườnu hơn 3: Nếu p là nghiệm tối ưu của phương trình (2.1) thì chúng ta có: Ằ = A = Ằr, -s lrong đó: „1 , I A, = £ ! / , - ' ( « ) - 4 ẢR = ieĩit/ I€R ữ (2.8) + 2 (4 )) J Chứng minh: Chúng ta thấy rằng phương trình (2.4) tương đương với Ằs = Â nếu .R chúng ta sử dụng định nghĩa đưa ra bời phương trình (2.8) và (2.9) và lưu ý rằng: ieRj ieR a leN ieS Sử dụng các định nghĩa về các thành phần node [2] và lưu ý rằng: 0. ± l =\ / =l chúng ta có: •i = ị ấ k , - A l = 2 > - A ) ^ /= l Từ đó, sử dụng trường họp 2 ta thấy rằng x=xs . Lưu ý các định nghĩa được liệt kê theo trình tự dưới đây cho giá trị a tuỳ ý (> 0 ): S{a) = { i \ a > f \ ệ , ) ị (2.10) Ằs ( a ) = (2 .1 1 ) R, (a) = { / | / ( 0 ) > a + g(Ảs ( a) )ị (2.12) Rtl(a) = {/ \ /,(,)> a + g(Ăs(a)) > /(0)}, (2.13) I *,+ Y M , - /,■ '( « + ^ ( 4 («)))! I€lị/(a) N(a) = { i \ a < (2-14) /€/?„(a) /; (ự>,),) và a . Ngoài ra, với giá trị oc tối ưu chúng ta có: A —A —X —Ả(ị(ơ.) —Xị^(ct) . .s - -R “ Trên cơ sở các trường hợp ], 2 và 3 ở trên, rút ra thuật toán cân bằng tảidưới đây, trong đó đề cập tới các yêu cầu về tính toán. [Thuật toán 11 1. Sắp xếp các node 0 ( n logn) Sắp xếp các node sao cho f|(ội) < f2(< 2) - •• ^ fni^n)t> Nếu f|((Ị)|) + g(0) > 2. Xác định a O(n) khi đó không cần cân bằng tải. (Xem các lưu ý dưới đây) Tìm a sao cho Ảs(a)=ẰK (a) (ví dụ tìm bằng phương pháp tìm kiếm nhị phân). Các biếu thức dưới đây được tính lần lượt với giá trị a nói trên. S(a) = ị i ị a > f,(0,),} Ãs ( a ) = RJ («) = { If, (°) ^ a + g(J*(a ))ị ' Ra{a ) = {/'!./; (a + g(Ãỵ ịa)) > f ' (0)}, 'L a )= A ieKj(a) + I W “ / l' ' ( fl + ẵ ( 4 ( fl)))] ieRa{a) 12 3. Xác định tải tối ưu 0(n) fìỊ - 0. với i e Rd (a), /3' =f'~'(a + g{Ả)), với j3,=f,~'{ocị ieS(a), [ỉ = ộ . với với i e R a(a), ieN(a), với, N( a) = { i \ a < f \ ộ l ) < a + g(Ảs (a))} Lưu ý : Quá trình xử lý chính của thuật toán là xác định a (trong bước 2). Thuật toán đơn điếm của Tantawi và Towsley xác định các thành phần của node trước khi tính a một cách chính xác. Thuật toán của chúng tôi khống đòi hỏi quá trình phàn chia node riêng rẽ và có thê thay vào đó là xác định phân chia các node trong quá trình xác định a. Các yêu cầu tính toán ở trên tưưng ứng với số node là n. Trong bước 2, tuy vậy, các yêu cầu tính toán tãng lên khi sai số cho phép của a giảm. Nếu phương pháp tìm kiếm nhị phàn được sử dụng thì các yêu cầu tính toán là 0 ( n log 1/s) trong đó s biếu diễn sai số cho phép. Chúng ta tiếp tục xem xét một số trường hợp sau: Trường hơn 4 : hàm số Ằ ) tăng (từ 0) và Ằ (a ) giảm (từ 0 ) một cách đơn điệu .s(a .K khi a tăng. Chứng minli: trường hợp này có thể chứng minh đơn giản từ định nghĩa (2.11) và (2.14) và giả thiết của f,(a) và g(A.). Chú ý: trường hợp này đảm bảo rằng thuật toán có thể xác định a thoả mãn Ằs(a) =ẢR(ct). Trường hơp 5 : với giá trị a bất kỳ thoả mãn a , < a < a 2, R j(a) = Rd(a ,) nêu Rd(a ,) = R j(a 2), R,(a) = Ra(a,) nếu Ra(a ,) = Ra( a 2), N(a) = N (a,) nếu N (aị) = N (a 2), S(a) = S(a,) nếu S(a,) = S(a2) 13 Chứng minh: ta có R,|(a) = R^otị) với giá trị bất kỳ của a (a, < a < a 2) nếu R,i(a,) = R j(a 2). Sắp xếp các node sao cho: f , ( 0 ) > f 2( 0 ) > f \ ( 0 ) > ..... >f„(0) Rti(a,) = Rd( a 2) hàm ý rằng f,(0) > a , + g(Às(a,)) > f1+ l(0) và f,(0) > a 2 + g(Ằ.s( a 2)) > f,+i(0) với cùng giá trị của i. Từ trường hợp 4 và giả thiết trên g(A.) chúng ta thấy rằng: c a , + g(Às(a,)) < a + g(Ầ.s(a)) < a 2 + g(Às( a 2)) Do vậy: f,(0) > a + g(Ầs(a)) > fI+|(0), điều đó có nghĩa là : R j(a) = Rt|(a,) = R j(a 2) Các biếu thức còn lại cũng được chứng minh tương tự. Trên cơ sớ của các vấn đề nêu ở trên, chúng ta có phiên bản khác của thuật toán có thế hoàn chinh hơn và yêu cầu ít thời gian tính toán hơn. 2.2.4 So sánh đặc tính thuật toán cân bằng tải. Chương trình FOTRAN dược viết để áp dụng thuật toán Tantawi và Towsley (T&T), thuật toán 1 (K & K 1) như ở trên và thuật toán r (K&K1’) được xây dựng lại từ thuật toán 1 kết hợp với trường hợp 5. Số bước chương trình của thuật toán 1 và r bằng khoáng 1/3 hoặc 2/3 số bước của thuật toán Tantawi và Towsley. Bang 2 .1 so sánh đặc tính của các thuật toán với mô hình phân tán bao gồm 10 node nối với nhau bởi mạng đơn kênh. Các kênh được mỏ hình hoá như hệ thống hàng đợi M/M/I 1111 Mỗi node được mô hình như là mô hình máy chủ trung tâm. Cách . phân chia tối ưu các node là: một chim (S), hai trung lập (N), 5 nguồn hoạt động (Ra) và 2 nguồn rỗi (Rj). Thời gian biên dịch và thời gian tính toán của các thuật toán đã được liệt kê ở trên, 8 là sai số cho phép của a. Bảng 2.1 : Thời gian biên dịch và thời gian tính toán của các thuật toán. Thuật toán T&T K & KI K & K I’ Thời gian biên dịch (giây) 2,11 0.78 0,92 e = 102 3,07 1,88 1,82 14 Thời gian tính toán (mili giây) 10' 104 10'5 3,66 3,24 3,80 2,10 2,65 2,86 1,98 2,53 2,39 10'6 4,17 3,30 2,87