Length-matching routing for high-speed printed circuit boards

Muhammet Mustafa Ozdal, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

27 Citations (Scopus)


As the clock frequencies used in industrial applications increase, the timing requirements imposed on routing problems become tighter. So, it becomes important to route the nets within tight minimum and maximum length bounds. Although the problem of routing nets to satisfy maximum length constraints is a well-studied problem, there exists no sophisticated algorithm in the literature that ensures that minimum length constraints are also satisfied. In this paper, we propose a novel algorithm that effectively incorporates the min-max length constraints into the routing problem. Our approach is to use a Lagrangian relaxation framework to allocate extra routing resources around nets simultaneously during routing them. We also propose a graph model that ensures that all the allocated routing resources can be used effectively for extending lengths. Our routing algorithm automatically prioritizes resource allocation for shorter nets, and length minimization for longer nets so that all nets can satisfy their min-max length constraints. Our experiments demonstrate that this algorithm is effective even in the cases where length constraints are tight, and the layout is dense.

Original languageEnglish
Title of host publicationProceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003
Place of PublicationUnited States
Number of pages7
ISBN (Print)9781581137620
Publication statusPublished - Nov 2003
Event2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003 - DoubleTree Hotel, San Jose, United States
Duration: 9 Nov 200313 Nov 2003
https://ieeexplore.ieee.org/xpl/conhome/8895/proceeding (Conference proceedings)

Publication series

NameProceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD
ISSN (Print)1092-3152


Conference2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Length-matching routing for high-speed printed circuit boards'. Together they form a unique fingerprint.

Cite this