Extended Maximal Matching Algorithm in High-Speed Switches

XU Yang; TANG Yi; WEN Zhen-kun; LIU Bin

您当前的位置：

首页 >

文章列表页 >

Extended Maximal Matching Algorithm in High-Speed Switches

更新时间：2025-07-16

- Extended Maximal Matching Algorithm in High-Speed Switches
- Acta Electronica Sinica Vol. 35, Issue 10, Pages: 1809-1816(2007)
- 作者机构：
  
  1. 清华大学计算机科学与技术系,北京,100084
  2. 深圳大学计算机系,广东,深圳,518055
  3. 清华大学计算机科学与技术系北京,100084
  4. 深圳大学计算机系广东深圳,518055
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393.05
- Published：2007
- 稿件说明：
移动端阅览
XU Yang, TANG Yi, WEN Zhen-kun, et al. Extended Maximal Matching Algorithm in High-Speed Switches[J]. Acta Electronica Sinica, 2007, 35(10): 1809-1816.
DOI：

XU Yang, TANG Yi, WEN Zhen-kun, et al. Extended Maximal Matching Algorithm in High-Speed Switches[J]. Acta Electronica Sinica, 2007, 35(10): 1809-1816. DOI：

摘要

调度算法是决定交换结构性能和实现复杂度的重要因素

极大匹配算法在这两方面存在不足.本文提出一类广义极大匹配(EMM)算法

使用不同权值参数能够派生出不同子类的算法.对广义极大匹配算法的研究从两方面展开

首先在2倍数据加速比下证明任何EMM(2)算法都能取得100％的吞吐量

并通过仿真表明能够取得与理想输出排队相近的延时性能;其次在没有加速比的条件下通过仿真表明具有2个以上权值参数的广义极大匹配算法能够大大提高极大匹配算法的吞吐量性能.

Abstract

Scheduling algorithms make a great impact on the performance and implementation complexity of switch architecture.Traditional maximal matching (MM) algorithm cannot get a proper balance between these two factors

so in this paper we propose a new kind of Extended Maximal Matching (EMM) algorithm.By using different weight parameters

EMM algorithm can derive different kinds of algorithms.We prove that any EMM(2) algorithm with data speedup of 2 can deliver 100% throughput

and show it can also achieve almost the same delay performance as ideal Output Queueing (OQ).Furthermore

under the situation of non-speedup

through simulation we show EMM algorithms

with more than two weight parameters

can greatly increase the throughput performance of MM algorithm.

关键词

Keywords

references

Views

1037

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Novel Cross-layer Design Scheme for Distributed Cooperative Communication Networks

Co-Scheduling Threads in SMT Processors Fairly

A QoS-Based Scheduling Algorithm for Concurrent Transactional Workflows

Polling-on-Demand Scheduling Algorithm for Bluetooth Piconet and Performance Evaluation

Related Author

YUE Dian-wu

XU Feng

ZHANG Min-xuan

SUN Cai-xia

LI Hui

GUO Yun-fei

WANG Bin-qiang

YI Peng

Related Institution

National Mobile Communications Research LaboratorySoutheast UniversityNanjingJiangsu 210096China

School of Information Science and TechnologyDalian Maritime UniversityDalianLiaoning 116026China

National Mobile Communications Research Laboratory,Southeast University

School of Information Science and Technology,Dalian Maritime University

College of Computer, National University of Defense Technology

⁰