Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Design of Next-Generation Routers and IP Networks
KTH, School of Electrical Engineering (EES), Communication Networks.
2008 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

This thesis investigates distributed router architectures and IP networks with centralized control. While the current trend in IP-router architectures is towards decentralized design, there have also been research proposals for centralizing the control functions in IP networks. With continuous evolution of routers and IP networks, we believe that eventually IP networks in an autonomous system (AS) and a distributed router might converge into one network system. This system, which can be considered both as a distributed router and a centrally-controlled IP network, is divided into a control plane and a forwarding plane. The control plane is responsible for routing, management and signalling protocols, while the forwarding plane is responsible for forwarding packets.

The work in this thesis covers both the forwarding and control planes. In the forwarding plane, we study network processor systems that function as forwarding elements in a distributed router. We introduce a system model and a simulation tool based on the model. Using the simulation tool, we investigate network processor system design by studying throughput, utilization, queueing behavior and packet delays. In addition to network processor systems, we study IP-address lookup, which is one of the key packet processing functions in Internet routers. Our work in IP-address lookup contains an efficient lookup algorithm, a scheme to divide the lookup procedure into two-stages in a distributed router, and an approach to perform efficient lookup on a router supporting multiple virtual routers.

In the control plane, we study three emerging research issues with centralized control. We provide a thorough study of the routing convergence process in networks with centralized control, and compare it with decentralized link-state routing protocols. We propose an efficient approach to perform traffic engineering and routing in networks with centralized control, and compare it with an approach using optimized link weights. Finally, we present an approach to perform loop-free updates of forwarding tables when the forwarding paths change. This loop-free update approach is particularly useful in networks with centralized control.

The results presented in this thesis are useful for building next-generation routers and IP networks with centralized control that might eventually converge into one network system.

Place, publisher, year, edition, pages
Stockholm: KTH , 2008. , vii, 34 p.
Series
Trita-EE, ISSN 1653-5146 ; 2008:040
Keyword [en]
router architecture, IP-network architecture
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-9381OAI: oai:DiVA.org:kth-9381DiVA: diva2:113771
Public defence
2008-11-26, M1, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Note
QC 20100726Available from: 2008-11-03 Created: 2008-10-28 Last updated: 2010-07-26Bibliographically approved
List of papers
1. Designing and Evaluating Network Processor Applications
Open this publication in new window or tab >>Designing and Evaluating Network Processor Applications
2005 (English)In: IEEE Workshop on High Performance Switching and Routing: Hong Kong, PEOPLES R CHINA, MAY 12-14, 2005, 2005, 142-146 p.Conference paper, Published paper (Refereed)
Abstract [en]

Network processors try to achieve the performance of traditional ASICs while providing programmability of general-purpose processors. In short, a network processor provides a programming interface for implementing packet forwarding services. It is therefore important to study how efficient different designs are, as well as investigate how difficult they are to program. In this paper, a network processor model is introduced which is used as a basis for a simulation tool. By sending packets into the simulator, throughput, latency, and utilization can be measured. An IPv4 forwarding application is evaluated using two different processing element topologies: a pipelined and a pooled. In addition, the performance impact of using multiple threads inside a single processing element is evaluated. The results show that the use of parallelism is crucial to achieve high performance, but that both the pipelined topology and pooled topology achieve comparable performance.

Keyword
network processors; parallel processing; pipeline processing; performance evaluation
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9329 (URN)10.1109/HPSR.2005.1503211 (DOI)000231187500029 ()2-s2.0-27644566537 (Scopus ID)
Note
QC 20100726Available from: 2008-10-30 Created: 2008-10-20 Last updated: 2013-06-12Bibliographically approved
2. Queueing Behavior and Packet Delays in Network Processor Systems
Open this publication in new window or tab >>Queueing Behavior and Packet Delays in Network Processor Systems
2007 (English)In: 15th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems: Bogazici Univ, Dept Comp Engn, Istanbul, TURKEY, OCT 24-26, 2007 / [ed] Caglayan M. U.; Field AJ; Gelenbe E., 2007, 217-224 p.Conference paper, Published paper (Refereed)
Abstract [en]

Network processor systems provide the performance of ASICs combined withthe programmability of general-purpose processors. One of the main challengesin designing these systems is the memory subsystem used when forwarding andqueueing packets. In this work, we study the queueing behavior and packet delaysin a network processor system which works as a router. We introduce a systemmodel and a simulation tool based on the model. Using the simulation tool, bothbest-effort and diffserv IPv4 forwarding were modeled and tested using real-worldand synthetically generated packet traces. The results on queueing behavior havebeen used to dimension various queues, and can be used as guidelines for designingmemory subsystems and queueing disciplines. In particular, a system withsmall queue sizes has been proposed. The results on packet delays also show thatour diffserv setup provides good service differentiation for best-effort and prioritypackets. Finally, the study reveals that the choice of traces has a large impact onthe results when evaluating router and switch architectures.

Series
International Symposium on Modeling Analysis and Simulation of Computer and Telecommunication Systems Proceedings, ISSN 1526-7539
Keyword
network processor; router; queueing behavior
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9330 (URN)10.1109/MASCOTS.2007.56 (DOI)000265212400031 ()2-s2.0-57849125895 (Scopus ID)978-1-4244-1853-4 (ISBN)
Note
QC 20100726Available from: 2008-10-20 Created: 2008-10-20 Last updated: 2013-09-09Bibliographically approved
3. Improving and Analyzing LC-Trie Performance for IP-Address Lookup
Open this publication in new window or tab >>Improving and Analyzing LC-Trie Performance for IP-Address Lookup
2007 (English)In: Journal of Networks, ISSN 1796-2056, Vol. 2, no 3, 18-27 p.Article in journal (Refereed) Published
Abstract [en]

IP-address lookup is a key processing function of Internet routers. The lookupis challenging because it needs to perform a longest prefix match. In this paper, wepresent our modifications to an efficient lookup algorithm, the LC-trie, based ona technique called prefix transformation. Thereafter, the LC-trie’s performance isanalyzed for both the original and our modified algorithm using real and syntheticallygenerated traces. The performance study includes trie search depth, prefixvector access behavior, cache behavior and packet lookup time. The study is basedboth on experiments and a model for packet lookup time. The results show thatthe modified algorithm requires only 30% of the lookup time of the original algorithm.In particular, the modified algorithm is capable of performing 60 millionpacket lookups per second on a Pentium 4, 2.8 GHz, computer for a real traffictrace. Further, the results show that the performance is about five times better onthe real trace compared to a synthetically generated network trace. This illustratesthat the choice of traces may have a large influence on the results when evaluatinglookup algorithms.

Keyword
IP-address lookup, trie, prefix transformation, performance evaluation
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9411 (URN)2-s2.0-51049091794 (Scopus ID)
Note
QC 20100726Available from: 2008-10-30 Created: 2008-10-30 Last updated: 2013-09-09Bibliographically approved
4. Two Stage IP-address Lookup in Distributed Routers
Open this publication in new window or tab >>Two Stage IP-address Lookup in Distributed Routers
2008 (English)In: Proc. of IEEE INFOCOM High-Speed Netwworks Workshop, 2008Conference paper, Published paper (Refereed)
Abstract [en]

IP-address lookup is the primary processing functionof Internet routers. While a wide range of algorithms havebeen developed to perform lookups, very few of them havethe distributed architecture of current and future routers inconsideration. To support rapidly increasing high data rates,packet processing in commercial routers today are divided intoan ingress and an egress part, with the lookup performed at theingress. In the lookup, the egress line card, the outgoing interfaceand the nexthop address of a given packet are determined. In thispaper, we propose an alternative scheme to perform the lookupby dividing the task, which is named two-stage lookup scheme.In the lookup, the ingress determines the egress only, then it is upto the egress to determine the outgoing interface and the nexthopaddress. Based on our analysis and experimental study, weconclude that the proposed scheme has several advantages in bothhardware lookup technologies and software lookup algorithms.In particular, it provides significantly more efficient high-speedpacket lookup.

Series
Infocom : proceedings, ISSN 0743-166X
Keyword
Computer networks; Data processing; Internet protocols; Address lookup; Infocom; Two stages
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9331 (URN)10.1109/INFOCOM.2008.4544582 (DOI)2-s2.0-51049092780 (Scopus ID)978-142442219-7 (ISBN)
Conference
2008 IEEE INFOCOM Workshops; Phoenix, AZ; 13 April 2008 through 18 April 2008
Note
QC 20100726Available from: 2008-10-30 Created: 2008-10-20 Last updated: 2013-09-09Bibliographically approved
5. Efficient IP-Address Lookup with a Shared Forwarding Table for Multiple Virtual Routers
Open this publication in new window or tab >>Efficient IP-Address Lookup with a Shared Forwarding Table for Multiple Virtual Routers
2008 (English)In: 2008 ACM CoNEXT Conference: 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08; Madrid; 9 December 2008 through 12 December 2008, 2008Conference paper, Published paper (Refereed)
Abstract [en]

Virtual routers are a promising way to provide network services such as customerspecificrouting, policy-based routing, multi-topology routing, and network virtulization.However, the need to support a separate forwarding information base (FIB)for each virtual router leads to memory scaling challenges. In this paper, wepresent a small, shared data structure and a fast lookup algorithm that capitalize onthe commonality of IP prefixes between each FIB. Experiments with real packettraces and routing tables show that our approach achieves much lower memoryrequirements and considerably faster lookup times. Our prototype implementationin the Click modular router, running both in user space and in the Linux kernel,demonstrates that our data structure and algorithm are an interesting solution forbuilding scalable routers that support virtualization.

Keyword
IP-address lookup; Virtual routers
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9412 (URN)10.1145/1544012.1544033 (DOI)2-s2.0-70350764027 (Scopus ID)978-160558210-8 (ISBN)
Note
QC 20100726Available from: 2008-10-30 Created: 2008-10-30 Last updated: 2010-07-26Bibliographically approved
6. Intra-Domain Routing Convergence with Centralized Control
Open this publication in new window or tab >>Intra-Domain Routing Convergence with Centralized Control
2009 (English)In: Computer Networks, ISSN 1389-1286, E-ISSN 1872-7069, Vol. 53, no 18, 2985-2996 p.Article in journal (Refereed) Published
Abstract [en]

The decentralized control scheme for routing in current IP networks has been questioned, and a centralized routing scheme has been proposed as an alternative. In this paper, we compare the convergence of centralized control scheme with decentralized link-state routing protocols. We first review the architectural advantages and challenges of centralized control. Thereafter, we identify and discuss the components of the convergence time in both schemes. We present how to achieve fast routing convergence in networks with centralized control. in particular, we analyze how to distribute forwarding information efficiently. Finally, we perform simulation studies on the convergence time for both real and synthetic network topologies and study the impact of control element location, link weights, and number of failures on the convergence time. The results show that the centralized control scheme can provide faster routing convergence than link-state routing protocols.

Keyword
Routing convergence; Centralized control; Link-state routing protocols
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9437 (URN)10.1016/j.comnet.2009.07.008 (DOI)000272862600002 ()2-s2.0-70449526570 (Scopus ID)
Note
QC 20100726. Uppdaterad från submitted till published (20100726).Available from: 2008-11-03 Created: 2008-11-03 Last updated: 2013-09-09Bibliographically approved
7. Traffic Engineering and Routing in IP Networks with Centralized Control
Open this publication in new window or tab >>Traffic Engineering and Routing in IP Networks with Centralized Control
2008 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 4982, 633-641 p.Article in journal (Refereed) Published
Abstract [en]

There have been research initiatives in centralized control recently, which advocatethat the control of an autonomous system (AS) should be performed in acentralized fashion. In this paper, we propose an approach to perform traffic engineeringand routing in networks with centralized control, named LP-redirect.LP-redirect is based on an efficient formulation of linear programming (LP) thatreduces the number of variables and constraints. As LP is not fast enough for runtimerouting, LP-redirect uses a fast scheme to recompute routing paths when anetwork topology changes. The performance evaluation of LP-redirect shows thatit is more efficient in both traffic engineering and computation than an approachusing optimized link weights. In addition, LP-redirect is suitable for runtime trafficengineering and routing.

Keyword
traffic engineering; routing; centralized control
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9414 (URN)10.1007/978-3-540-79549-0_55 (DOI)000255924000055 ()2-s2.0-44649200684 (Scopus ID)
Note
QC 20100726. Uppdaterad från konferensbidrag till artikel (20100726).Available from: 2008-10-30 Created: 2008-10-30 Last updated: 2013-09-09Bibliographically approved
8. Loop-Free Updates of Forwarding Tables
Open this publication in new window or tab >>Loop-Free Updates of Forwarding Tables
2008 (English)In: IEEE Transactions on Network and Service Management, ISSN 1932-4537, Vol. 5, no 1, 22-35 p.Article in journal (Refereed) Published
Abstract [en]

When the forwarding paths in an IP network change due to a link failure or a link weight modification, the forwarding tables in the routers may need to be updated. Each of these updates may cause transient loops if they are not performed in an appropriate order. In this paper, we propose an order to update the forwarding tables that avoids transient loops for non-urgent changes. The order is obtained by studying the changes in the forwarding tables, therefore it can be used in networks running any routing protocols, and for any type of forwarding path changes. After presenting the order, we prove that it is correct, and present an efficient algorithm to compute the order. Thereafter, we present several algorithms for performing forwarding table updates in accordance with the order. We also discuss how the update algorithms can be applied to both networks with centralized control and decentralized routing protocols. Finally, we study the update algorithms’ performance on several network topologies and with varying parameter settings and for several types of forwarding path changes.

Keyword
Configuration management; FIB updates; Network management; Transient routing loops
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-9328 (URN)10.1109/TNSM.2008.080103 (DOI)2-s2.0-49049121685 (Scopus ID)
Note
QC 20100726Available from: 2008-10-30 Created: 2008-10-20 Last updated: 2013-09-09Bibliographically approved

Open Access in DiVA

fulltext(268 kB)1038 downloads
File information
File name FULLTEXT02.pdfFile size 268 kBChecksum SHA-512
aa54cbe3c01a62a805b08ce217a256fdcb1b4fc76dda039ae9bf9eb0556d1c23bb25ba181e5e0153ca52f6bf42a9f67f3e40a10094594d4ac9c063cddb63fdb8
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Fu, Jing
By organisation
Communication Networks
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar
Total: 1039 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 646 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf