論文の概要: Learning in Strategic Queuing Systems with Small Buffers
- arxiv url: http://arxiv.org/abs/2502.08898v1
- Date: Thu, 13 Feb 2025 02:23:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-14 13:44:21.529588
- Title: Learning in Strategic Queuing Systems with Small Buffers
- Title(参考訳): 小さなバッファを持つ戦略的キューシステムにおける学習
- Authors: Ariana Abel, Yoav Kolumbus, Jeronimo Martin Duque, Eva Tardos,
- Abstract要約: キューが学習していると、中央で調整すれば必要なものに比べて、サーバの容量が一定に増加し、システムの安定を維持するのに十分であることを示す。
この研究は、ラウンド間の輸送効果を持つシステムにおける利己的な学習の影響に関する文献の増大に貢献している。
- 参考スコア(独自算出の注目度): 3.6480791907166306
- License:
- Abstract: Routers in networking use simple learning algorithms to find the best way to deliver packets to their desired destination. This simple, myopic and distributed decision system makes large queuing systems simple to operate, but at the same time, the system needs more capacity than would be required if all traffic were centrally coordinated. In a recent paper, Gaitonde and Tardos (EC 2020 and JACM 2023) initiate the study of such systems, modeling them as an infinitely repeated game in which routers compete for servers and the system maintains a state (number of packets held by each queue) resulting from outcomes of previous rounds. Queues get to send a packet at each step to one of the servers, and servers attempt to process only one of the arriving packets, modeling routers. However, their model assumes that servers have no buffers at all, so queues have to resend all packets that were not served successfully. They show that, even with hugely increased server capacity relative to what is needed in the centrally-coordinated case, ensuring that the system is stable requires using timestamps and priority for older packets. We consider a system with two important changes, which make the model more realistic: first we add a very small buffer to each server, allowing it to hold on to a single packet to be served later (even if it fails to serve it); and second, we do not require timestamps or priority for older packets. Our main result is to show that when queues are learning, a small constant factor increase in server capacity, compared to what would be needed if centrally coordinating, suffices to keep the system stable, even if servers select randomly among packets arriving simultaneously. This work contributes to the growing literature on the impact of selfish learning in systems with carryover effects between rounds: when outcomes in the present round affect the game in the future.
- Abstract(参考訳): ネットワークのルータは、単純な学習アルゴリズムを使用して、パケットを所望の目的地に届ける最善の方法を見つける。
この単純で、ミオピックで分散的な決定システムは、大規模なキューシステムを操作しやすくするが、同時に、全てのトラフィックが集中的に調整された場合よりも、必要以上の容量を必要とする。
最近の論文では、Gaitonde と Tardos (EC 2020 と JACM 2023) がそのようなシステムの研究を開始し、それらをルータがサーバと競合する無限に繰り返されるゲームとしてモデル化し、システムは前回のラウンドの結果、状態(キューが保持するパケット数)を維持する。
キューは各ステップのパケットをサーバの1つに送信し、サーバは受信したパケットの1つだけを処理し、ルータをモデル化する。
しかし、彼らのモデルはサーバにバッファが全くないことを前提としており、キューは正常に提供されていないすべてのパケットを再送する必要がある。
彼らは、中央協調型のケースで必要とされるものと比較してサーバー容量が大幅に増大しているにもかかわらず、システムが安定していることを保証するには、古いパケットに対してタイムスタンプと優先順位を使用する必要があることを示した。
まず、各サーバに非常に小さなバッファを追加し、1つのパケットを後から(サービスに失敗しても)保留できるようにし、次に、古いパケットにタイムスタンプや優先順位を必要としないようにする。
我々の主な成果は、キューが学習している場合、サーバが同時に到着したパケットの中からランダムに選択したとしても、中央にコーディネートしてシステムの安定を維持するのに必要なものと比較して、サーバの容量が一定に増加することを示すことである。
この研究は、ラウンド間の移動効果を持つシステムにおける利己的な学習の影響に関する文献の増大に貢献している。
関連論文リスト
- Asynchronous Multi-Server Federated Learning for Geo-Distributed Clients [4.6792910030704515]
フェデレートラーニング(FL)システムは、複数のクライアントが単一のサーバで中間モデルの重みを同期的に交換することで、機械学習モデルを反復的にトレーニングすることができる。
このようなFLシステムのスケーラビリティは、同期通信によるサーバアイドル時間と、ひとつのサーバがボトルネックになるリスクの2つの要因によって制限することができる。
本稿では,完全に非同期な新しいFLアーキテクチャを提案する。
論文 参考訳(メタデータ) (2024-06-03T15:29:46Z) - Communication Efficient ConFederated Learning: An Event-Triggered SAGA
Approach [67.27031215756121]
Federated Learning(FL)は、さまざまなデータソース上のローカルデータを収集することなく、モデルトレーニングをターゲットとする機械学習パラダイムである。
単一のサーバを使用するStandard FLは、限られた数のユーザしかサポートできないため、学習能力の低下につながる。
本研究では,多数のユーザに対応するために,emphConfederated Learning(CFL)と呼ばれるマルチサーバFLフレームワークを検討する。
論文 参考訳(メタデータ) (2024-02-28T03:27:10Z) - RelayAttention for Efficient Large Language Model Serving with Long System Prompts [59.50256661158862]
本稿では,長いシステムプロンプトを含むLCMサービスの効率を向上させることを目的とする。
これらのシステムプロンプトの処理には、既存の因果注意アルゴリズムにおいて、大量のメモリアクセスが必要である。
本稿では,DRAMから入力トークンのバッチに対して,DRAMから隠れた状態を正確に1回読み取ることのできるアテンションアルゴリズムであるRelayAttentionを提案する。
論文 参考訳(メタデータ) (2024-02-22T18:58:28Z) - Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems [21.944723061337267]
我々は、中央キューに到着するジョブをヘテロジニアスサーバのシステムに効率的にルーティングする問題を考察する。
均質なシステムとは異なり、キュー長が一定のしきい値を超えた場合、ジョブを遅いサーバにルーティングするしきい値ポリシーは、ワンファストワンスローの2サーバシステムに最適であることが知られている。
本稿では,低次元ソフトしきい値パラメータ化を用いた効率的なポリシー勾配に基づくアルゴリズムであるACHQを提案する。
論文 参考訳(メタデータ) (2024-02-02T05:22:41Z) - Learning While Scheduling in Multi-Server Systems with Unknown
Statistics: MaxWeight with Discounted UCB [18.898514227870926]
本稿では、複数のサーバと複数のタイプのジョブを持つマルチサーバシステムについて考察する。
目標は、処理時間の統計を知ることなく、サーバ上のジョブをスケジュールすることだ。
我々は,MaxWeightスケジューリングポリシと割引された高信頼度境界(UCB)を組み合わせることで,統計を同時に学習し,ジョブをサーバにスケジュールするアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-02T15:37:02Z) - Better than the Best: Gradient-based Improper Reinforcement Learning for
Network Scheduling [60.48359567964899]
パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。
我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
論文 参考訳(メタデータ) (2021-05-01T10:18:34Z) - Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud
System [54.588242387136376]
エッジクラウドシステムのための学習ベースのスケジューリングフレームワークkaisを紹介する。
まず,分散した要求ディスパッチに対応するために,協調型マルチエージェントアクタ-クリティックアルゴリズムを設計する。
次に,多種多様なシステムスケールと構造について,グラフニューラルネットワークを用いてシステム状態情報を埋め込む。
第3に、リクエストディスパッチとサービスオーケストレーションを調和させる2段階のスケジューリングメカニズムを採用します。
論文 参考訳(メタデータ) (2021-01-17T03:45:25Z) - Domain-specific Communication Optimization for Distributed DNN Training [10.781867496460837]
本稿では,DNN訓練の通信オーバーヘッドをきめ細かな方法で最適化するために,ディープラーニングのドメイン固有性を利用した新しいソリューションDLCPを提案する。
これは、SGDベースのトレーニングの有界損失耐性を利用して、勾配圧縮によって純粋に回避できない尾の通信遅延を改善する。
その後、フローレベルのスケジューリングとは対照的に、粒度の細かいパケットレベルの優先順位付けとドロップを行い、グレードの層や大きさに基づいて、精度に影響を与えることなくモデル収束をさらに高速化する。
論文 参考訳(メタデータ) (2020-08-16T09:53:21Z) - Superiority of Simplicity: A Lightweight Model for Network Device
Workload Prediction [58.98112070128482]
本稿では,歴史観測に基づく時系列予測のための軽量な解を提案する。
ニューラルネットワークと平均予測器という2つのモデルからなる異種アンサンブル法で構成されている。
利用可能なFedCSIS 2020チャレンジデータセットの総合的なR2$スコア0.10を達成している。
論文 参考訳(メタデータ) (2020-07-07T15:44:16Z) - Stability and Learning in Strategic Queuing Systems [0.0]
ゲームモデリングキューイングシステムのコンテキストにおける現象について検討する。
ルータはサーバと競合し、サービスを取得しないパケットは将来のラウンドで再送される。
本稿では,キューイングシステムにおける自己学習の効果を初めて研究する。
論文 参考訳(メタデータ) (2020-03-16T03:59:00Z) - Joint Parameter-and-Bandwidth Allocation for Improving the Efficiency of
Partitioned Edge Learning [73.82875010696849]
機械学習アルゴリズムは、人工知能(AI)モデルをトレーニングするために、ネットワークエッジにデプロイされる。
本稿では,パラメータ(計算負荷)割り当てと帯域幅割り当ての新しい共同設計に焦点を当てる。
論文 参考訳(メタデータ) (2020-03-10T05:52:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。