Change search
Refine search result
1 - 15 of 15
CiteExportLink to result list
Permanent 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Fu, Jing
    KTH, School of Electrical Engineering (EES).
    Design and evaluation of network processor systems and forwarding applications2006Licentiate thesis, comprehensive summary (Other scientific)
    Abstract [en]

    During recent years, both the Internet traffic and packet transmission rates have been growing rapidly, and new Internet services such as VPNs, QoS and IPTV have emerged. To meet increasing line speed requirements and to support current and future Internet services, improvements and changes are needed in current routers both with respect to hardware architectures and forwarding applications. High speed routers are nowadays mainly based on application specific integrated circuits (ASICs), which are custom made and not flexible enough to support diverse services. Generalpurpose processors offer flexibility, but have difficulties to in handling high data rates. A number of software IP-address lookup algorithms have therefore been developed to enable fast packet processing in general-purpose processors. Network processors have recently emerged to provide the performance of ASICs combined with the programmability of general-purpose processors.

    This thesis provides an evaluation of router design including both hardware architectures and software applications. The first part of the thesis contains an evaluation of various network processor system designs. We introduce a model for network processor systems which is used as a basis for a simulation tool. Thereafter, we study two ways to organize processing elements (PEs) inside a network processor to achieve parallelism: a pipelined and a pooled organization. The impact of using multiple threads inside a single PE is also studied. In addition, we study the queueing behavior and packet delays in such systems. The results show that parallelism is crucial to achieving high performance,but both the pipelined and the pooled processing-element topologies achieve comparable performances. The detailed queueing behavior and packet delay results have been used to dimension queues, which can be used as guidelines for designing memory subsystems and queueing disciplines.

    The second part of the thesis contains a performance evaluation of an IP-address lookup algorithm, the LC-trie. The study considers trie search depth, prefix vector access behavior, cache behavior, and packet lookup service time. For the packet lookup service time, the evaluation contains both experimental results and results obtained from a model. The results show that the LC-trie is an efficient route lookup algorithm for general-purpose processors, capable of performing 20 million packet lookups per second on a Pentium 4, 2.8 GHz computer, which corresponds to a 40 Gb/s link for average sized packets. Furthermore, the results show the importance of choosing packet traces when evaluating IP-address lookup algorithms: real-world and synthetically generated traces may have very different behaviors.

    The results presented in the thesis are obtained through studies of both hardware architectures and software applications. They could be used to guide the design of next-generation routers.

  • 2.
    Fu, Jing
    KTH, School of Electrical Engineering (EES), Communication Networks.
    On the Design of Next-Generation Routers and IP Networks2008Doctoral 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.

  • 3.
    Fu, Jing
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Hagsand, Olof
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    A Programming Model for a Forwarding Element2004In: 2nd Swedish National Computer Networking Workshop, SNCNW 2004, Karlstad, Sweden, 2004, p. 59-65Conference paper (Refereed)
    Abstract [en]

    The architectural complexity and diversity of current

    network devices make them complex to manage and

    difficult to program. In this work, we specify a

    programming model for network devices that function as

    forwarding elements. We first identify the key packet

    processing functions and analyze current network

    devices. Next, we derive a model that consists of

    processing blocks

    to represent simple packet processing

    functions running on a forwarding element. We further

    use a

    processing block topology

    to represent how the

    individual packet processing functions are interconnected

    on the datapath. We also demonstrate how to program a

    forwarding element and show an example IPv4

    forwarding service implementation. Finally, we evaluate

    programmability and the performance of the FE model.

  • 4.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Designing and Evaluating Network Processor Applications2005In: IEEE Workshop on High Performance Switching and Routing: Hong Kong, PEOPLES R CHINA, MAY 12-14, 2005, 2005, p. 142-146Conference 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.

  • 5.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks.
    An analysis of Queueing Behavior in Network Processor Systems2006In: 4th Swedish National Computer Networking Workshop, SNCNW 2006, Luleå, Sweden, 2006Conference paper (Refereed)
  • 6.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC).
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Improving and Analyzing LC-Trie Performance for IP-Address Lookup2007In: Journal of Networks, ISSN 1796-2056, E-ISSN 1796-2056, Vol. 2, no 3, p. 18-27Article in journal (Refereed)
    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.

  • 7.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Performance Evaluation and Cache Behavior of LC-Trie for IP-Address Lookup2006In: Proc. of IEEE 2006 Workshop on High Performance Switching and Routing (HPSR 2006), IEEE , 2006, p. 29-35Conference paper (Refereed)
    Abstract [en]

    Many IP-address lookup software algorithms use a trie-like data structure to perform longest prefix match. LC-trie is an efficient algorithm that uses level compression and path compression on tries. By using realistic and synthetically generated traces, we study the performance of the LC-trie algorithm. Our study includes trie search depth, prefix vector access behavior, cache behavior, and packet lookup service time. The results show that for a realistic traffic trace, the LC-trie algorithm is capable of performing 20 million packet lookups per second on a Pentium 4, 2.8 GHz computer, which corresponds to a 40 Gb/s link for average sized packets. Further, the results show that LC-trie performs up to five times better on the realistic trace compared to a synthetically generated network trace. This illustrates that the choice of traces may have a large influence on the results when evaluating lookup algorithms.

  • 8.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Hagsand, Olof
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
    Queueing Behavior and Packet Delays in Network Processor Systems2007In: 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, p. 217-224Conference 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.

  • 9.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Rexford, Jennifer
    Princeton University.
    Efficient IP-Address Lookup with a Shared Forwarding Table for Multiple Virtual Routers2008In: 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 (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.

  • 10.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Sjödin, Peter
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Convergence of intra-domain routing with centralized control2008In: AD HOC AND SENSOR NETWORKS, WIRELESS NETWORKS, NEXT GENERATION INTERNET, PROCEEDINGS, 2008, Vol. 4982, p. 518-529Conference paper (Refereed)
    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 identify the components of the convergence time. Thereafter, we study 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.

  • 11.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Sjödin, Peter
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Telecommunication Systems Laboratory, TSLab.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Intra-Domain Routing Convergence with Centralized Control2009In: Computer Networks, ISSN 1389-1286, E-ISSN 1872-7069, Vol. 53, no 18, p. 2985-2996Article in journal (Refereed)
    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.

  • 12.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Sjödin, Peter
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Telecommunication Systems Laboratory, TSLab.
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Loop-Free Updates of Forwarding Tables2008In: IEEE Transactions on Network and Service Management, ISSN 1932-4537, Vol. 5, no 1, p. 22-35Article in journal (Refereed)
    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.

  • 13.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
    Sjödin, Peter
    KTH, School of Information and Communication Technology (ICT).
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
    Traffic Engineering and Routing in IP Networks with Centralized Control2008In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 4982, p. 633-641Article in journal (Refereed)
    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.

  • 14.
    Fu, Jing
    et al.
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Sjödin, Peter
    KTH, School of Information and Communication Technology (ICT).
    Karlsson, Gunnar
    KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
    Two Stage IP-address Lookup in Distributed Routers2008In: Proc. of IEEE INFOCOM High-Speed Netwworks Workshop, 2008Conference 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.

  • 15. Shi, L.
    et al.
    Fu, Jing
    KTH, School of Electrical Engineering (EES), Communication Networks.
    Fu, X.
    Loop-free forwarding table updates with minimal link overflow2009In: ICIEA: 2009 4th IEEE Conference on Industrial Electronics And Applications, 2009, p. 3960-3963Conference paper (Refereed)
    Abstract [en]

    The forwarding paths in an IP network may change due to a link failure, network equipment maintenance, or reconfiguration of link weights. The forwarding tables in the routers need then to be updated. These updates may cause transient loops and link overflow, if they are not performed in an appropriate order. While existing proposals achieve loop-free updates, transient link overflow is still a problem during the updating process. In this paper, we present a method that compares the initial and final forwarding paths, and obtains the updatable nodes that do not cause any transient loop or link overflow. However, this goal is not always achievable, therefore, we propose an algorithm to update the forwarding tables that will refrain the link overflows to a minimal level. The performance study on a real topology with two setups confirms that our approach achieves smaller link overflow than by using a previously proposed approach.

1 - 15 of 15
CiteExportLink to result list
Permanent 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