|
|
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
Задача, в общем, такова: Есть программа передающая файлы через сеть. Для каждого файла создается специальный класс, который передает данные через несколько соединений. Скорость передачи непосредственно зависит от количества соединений. Для каждого соединения создается своя нить. У класса есть функции: добавить одно соединение, и закрыть одно соединение. У каждого файла есть приоритет: высокий, средний или низкий. Общее количество соединений может быть ограничено. Подскажите алгоритм, который можно использовать для распределения соединений между файлами согласно их приоритетам. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2011, 18:20 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatXДля каждого файла создается специальный класс, который передает данные через несколько соединений. Специальный класс ? Может все-же объект? А вообще, твоя задача это классическая задача о рюкзаке: http://en.wikipedia.org/wiki/Knapsack_problem Принципы ее решения обсуждаются тут на форуме как минимум раз в месяц. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2011, 19:33 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
Но максимальное количество соединений может быть не ограничено, или ограничено, но неявно: например, пропускной способностью канала или загруженностью серверов на данный момент, а также их настройками. Задача о рюкзаке все еще подходит для решения этой проблемы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.12.2011, 22:15 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
Да и без этого, у меня не получается сопоставить задачу о рюкзаке с моей проблемой... Там же как я понял, есть рюкзак некоторого заданного объема, у предметов есть объем и стоимость, задача состоит в том чтобы в рюкзак набрать предметов на максимально возможную общую стоимость. Как это сопоставить с моей задачей я что-то не могу понять... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2012, 01:26 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
Ну а у тебя что? Есть пропускная способность физического канала. = объем рюкзака От нее зависит количество возможных соединений. = количество вещей Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей Тебе нужно передать как можно больше "важных" файлов и по возможности не забывать про "неважные". Так? Ну значит в самом начале - рюкзак пуст, набиваешь его. Как только один файл закончился, делаешь перераспределение - добиваешь оставшимися в очереди файлами в порядке их приоритета. Если хочешь чтобы важные файлы останавливали пересылку неважных - по приходу нового важного файла в очередь делаешь принудительную очистку всего рюкзака и заново его наполняешь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2012, 19:57 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
White OwlНу а у тебя что? Есть пропускная способность физического канала. = объем рюкзака От нее зависит количество возможных соединений. = количество вещей Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей А что тогда стоимость вещей? И где решение задачи: распределение количества соединений между файлами согласно их приоритету? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.01.2012, 20:29 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatXА что тогда стоимость вещей? И где решение задачи: распределение количества соединений между файлами согласно их приоритету?У тебя один файл посылается по нескольким соединениям одновременно или по одному? Если по нескольким - обзови количество соединений на один файл его стоимостью и все. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.01.2012, 01:10 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
White OwlУ тебя один файл посылается по нескольким соединениям одновременно или по одному? Если по нескольким - обзови количество соединений на один файл его стоимостью и все. Количество соединений на один файл - это та величина которую нужно найти. Нужен алгоритм, который в соответствии с приоритетами файлов устанавливает им нужные количества соединений. Это как закачки в uTorrent или DownloadMaster (там можно выставлять приоритеты закачек). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.01.2012, 01:29 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatXКоличество соединений на один файл - это та величина которую нужно найти.Хорошо. Файл размером один байт - сколько соединений нужно чтобы его переслать? Файл размером сто гигабайт - сколько соединений нужно чтобы его переслать? Два файла одинакового размера, но с разными приоритетами - насколько больше соединений будет у одного файла чем у другого? Сколько соединений ты в принципе можешь создать? Не забывай что у тебя всего одно физическое соединение с провайдером и чем больше логических соединений ты создашь - тем медленнее они все будут работать. Обойти ограничение физического канала в принципе не возможно. Из последнего и пляшем. Если мы изначально решим что на каждые сто килобайт файла с низким приоритетом мы будем создавать по одному соединению, на файлы со средним по два и с высоким по четыре (эти цифры я беру с потолка). То на очередь из допустим десяти файлов с разными приоритетами и разным объемом тебе понадобится Х соединений. Если это Х меньше чем максимально возможное количество соединений на твоем физическом канале - то хорошо. Если больше (и начинаются ощутимые тормоза), то какие-то файлы должны получить меньше соединений (по одному на двести килобайт?) либо вообще должны быть временно заморожены (это тебе решать что лучше). Когда и как часто ты будешь решать количество соединений? При поступлении файла в очередь? При уходе файла из очереди? Будешь ли ты пересчитывать и перераспределять соединения на уже обрабатывающийся файл или перераспределение на уже работающем файле невозможно? Ты все еще не видишь параллелей с рюкзаком? :) RedCatXНужен алгоритм, который в соответствии с приоритетами файлов устанавливает им нужные количества соединений. Это как закачки в uTorrent или DownloadMaster (там можно выставлять приоритеты закачек). Ты уверен что действительно нужно много соединений ? Множественные параллельные соединения это очень редко дает прирост в скорости и только на больших расстояниях. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.01.2012, 03:02 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
White OwlФайл размером один байт - сколько соединений нужно чтобы его переслать? Файл размером сто гигабайт - сколько соединений нужно чтобы его переслать? Файл разбивается на секции вне зависимости от его размера (но конечно файл в 1 байт разбить просто невозможно), для загрузки каждой секции открывается соединение. Во время передачи допустимо создавать новые секции или приостанавливать существующие, таким образом устанавливая количество соединений. Собственно нужно сделать чтобы файл с высоким приоритетом получал большее количество соединений чем файл с низким. Никаких ограничений нет, или они неизвестны. Как и когда перераспределять количество соединений я не знаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 01:04 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatX, Разве от количества соединений будет расти скорость передачи ? Или в задаче нужно передать один файл на несколько хостов-приемников ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 08:32 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
JoFanРазве от количества соединений будет расти скорость передачи ? Или в задаче нужно передать один файл на несколько хостов-приемников? Да, от количества соединений зависит скорость передачи. Попробуйте, например, скачать файл по HTTP сначала через одно соединение (встроенный в браузер менеджер загрузок), а потом скачайте его через несколько соединений (сторонний менеджер загрузок, например, ReGet). В первом случае скорость будет около 20% от пропускной способности вашего интернет-канала. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 13:23 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatXJoFanРазве от количества соединений будет расти скорость передачи ? Или в задаче нужно передать один файл на несколько хостов-приемников? Да, от количества соединений зависит скорость передачи. Попробуйте, например, скачать файл по HTTP сначала через одно соединение (встроенный в браузер менеджер загрузок), а потом скачайте его через несколько соединений (сторонний менеджер загрузок, например, ReGet). В первом случае скорость будет около 20% от пропускной способности вашего интернет-канала. такое поведение reget актуально было во время медленной модемной связи (уже и не помню зачем так сделано было), сейчас же для закачки больших файлов используется торрент технология но и в один поток я качаю равно со скоростью, указанной в тарифном плане (никакой уменьшении скорости не наблюдаю) возможно такое может быть, если на самом сайте идет ограничение на отдачу на коннект если же говорить о локальной сети, то тут качание в несколько соединений не оправдано предлагаю взять уже готовые средства для обмена (например http://curl.haxx.se/libcurl/), и только если вдруг (в чем я лично сомневаюсь) покажут себя плохо - изобретать свой велосипед ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 14:08 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
JoFanно и в один поток я качаю равно со скоростью, указанной в тарифном плане (никакой уменьшении скорости не наблюдаю) Вам очень повезло с вашим интернет провайдером. У меня, например, ни разу не получалось достичь скорости указанной в тарифе на одном HTTP-соединении. JoFanпредлагаю взять уже готовые средства для обмена (например http://curl.haxx.se/libcurl/), и только если вдруг (в чем я лично сомневаюсь) покажут себя плохо - изобретать свой велосипед Я и так использую библиотеку libcurl. Но задача состоит не в этом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 14:59 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatXПодскажите алгоритм, который можно использовать для распределения соединений между файлами согласно их приоритетам. Должна хорошо подойти идея жадного (greedy) алгоритма. Во-первых, уточняете понятие приоритета. Кроме базового (который Вы назвали) вычисляемый приоритет файла может регулироваться его размером и долей уже прокачанного содержимого. Ну а потом - файлы выстраиваются в приоритетную очередь, на нескольких первых высыпается соединений по необходимости. При освобождении соединений они добрасываются файлам, испытывающим дефицит, если таких нет - берётся очередной файл из очереди. При добавлении файла приоритетом выше минимального скачивающегося - тот возвращается в очередь либо с него срезаются соединения. Правила расчёта вычисляемого приоритета регулируют ситуации типа "этот файл низкоприоритетный, но уже почти скачан, глупо его тормозить". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 17:18 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
RedCatX, думаю здесь подойдёт система приоритетов которую использует eMule или torrent клиент. Процессы изначально обладают одинаковым приоритетом. В процессе закачки они захватывают слоты закачек (абстракция) настолько, насколько позволяет канал или политика сети. Пока есть активные процессы с высоким приоритетом, процессы с средним приоритетом слоты не берут и т.д. Между равными происходит захват слотов не знаю как но возможно по RoundRobin. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.01.2012, 20:58 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
Большое спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.01.2012, 14:20 |
|
||
|
Посоветуйте алгоритм распределения ресурсов
|
|||
|---|---|---|---|
|
#18+
White OwlНу а у тебя что? Есть пропускная способность физического канала. = объем рюкзака От нее зависит количество возможных соединений. = количество вещей Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей стоимость вещей Объем файла = объем вещи Тебе нужно передать как можно больше "важных" файлов и по возможности не забывать про "неважные". Так? Чем выше удельный приоритет (средний приоритет файлов в рюкзаке/объем файлов в рюкзаке) в рюкзаке тем лучше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2012, 15:28 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=37601240&tid=1342466]: |
0ms |
get settings: |
8ms |
get forum list: |
21ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
174ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
52ms |
get tp. blocked users: |
1ms |
| others: | 239ms |
| total: | 514ms |

| 0 / 0 |
