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
Scalable Matching and Ranking for Network Search
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
Cisco Systems, San Jose, USA.
2013 (English)In: 2013 9th International Conference on Network and Service Management (CNSM), IEEE Computer Society, 2013, 251-259 p.Conference paper, Published paper (Refereed)
Abstract [en]

Network search makes operational data available in real-time to management applications. In contrast to traditional monitoring, neither the data location nor the data format needs to be known to the invoking process, which simplifies application development, but requires an efficient search plane inside the managed system. The search plane is realized as a network of search nodes that process search queries in a distributed fashion. This paper introduces matching and ranking for network search queries. We are proposing a semantic for matching and ranking, which is configurable to support different types of management applications - from exact matching for database-style queries to loose, approximate matching, which is appropriate for exploratory purposes. We describe an echo protocol for efficient distributed query processing that supports matching and ranking. Further, we present the design of a search node, which maintains a real-time database of operational information and allows for parallel processing of search queries. A prototype implementation on a cloud testbed shows that the network search system, on a 9-node cluster with 24 core servers, executes 200 global search queries/sec with the 75th percetile latency below 100 milliseconds and with a CPU utilization below 5%. The performance measurements, together with our design, suggest that a system of 100,000 servers processing the same load would exhibit the same overhead per server and a query latency of below 1 sec.

Place, publisher, year, edition, pages
IEEE Computer Society, 2013. 251-259 p.
Keyword [en]
distributed management, distributed query processing, innetwork management, matching and ranking, Network search
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-128191DOI: 10.1109/CNSM.2013.6727844ISI: 000345853200042Scopus ID: 2-s2.0-84894467062ISBN: 978-3-901882-53-1 (print)OAI: oai:DiVA.org:kth-128191DiVA: diva2:647231
Conference
2013 9th International Conference on Network and Service Management, CNSM 2013 and its three collocated Workshops - ICQT 2013, SVM 2013 and SETM 2013; Zurich; Switzerland; 14 October 2013 through 18 October 2013
Note

QC 20130930

Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2016-04-11Bibliographically approved
In thesis
1. Real-Time Search in Large Networks and Clouds
Open this publication in new window or tab >>Real-Time Search in Large Networks and Clouds
2013 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Networked systems, such as telecom networks and cloud infrastructures, hold and generate vast amounts of conguration and operational data, only a small portion of which is used today by management applications. The overall goal of this work is to make all this data available through a real-time search process named network search , where queries are invoked, without giving the location or the format of the data, similar to web search. Such a capability will simplify many management applications and enable new classes of realtime management solutions. The fundamental problems in network search relate to search in a vast and dynamic information space and the fact that the information is distributed across a very large system.

The thesis contains several contributions towards engineering a network search system. We present a weakly-structured information model, which enables representation of heterogeneous network data, a keyword-based search language, which supports location- and schema-oblivious search queries, and a distributed search mechanism, which is based on an echo protocol and supports a range of matching and ranking options. The search is performed in a peer-to-peer fashion in a network of search nodes. Each search node maintains a local real-time database of locally sensed conguration and operational information. Many of the concepts we developed for network search are based on results from the elds of information retrieval, web search, and very large databases. The key feature of our solution is that the search process and the computation of the query results is performed on local data inside the network or the cloud. We have build a prototype of the system on a cloud testbed and developed applications that use network search functionality. The performance measurements suggest that it is feasible to engineer a network search system that processes queries at low latency and low overhead, and that can scale to a very large system in the order of 100,000 nodes.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. 87 p.
Series
Trita-EE, ISSN 1653-5146 ; 2013:35
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-128193 (URN)978-91-7501-879-9 (ISBN)
Presentation
2013-10-14, Lab 2, Osquldas Väg 10, KTH, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20130930

Available from: 2013-09-30 Created: 2013-09-10 Last updated: 2013-09-30Bibliographically approved
2. A Bottom-Up Approach to Real-Time Search in Large Networks and Clouds
Open this publication in new window or tab >>A Bottom-Up Approach to Real-Time Search in Large Networks and Clouds
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Networked systems, such as telecom networks and cloud infrastructures, generate and hold vast amounts of conguration and operational data. The goal of this work is to make all this data available through a real-time search process named network search , which will enable new real-time management solutions. The thesis contains several contributions towards engineering a network search system. Key elements of our design are a weakly structured information model that includes spatial properties, a query language that supports location- and schema-oblivious search queries, a peer-to-peer architecture, a set of echo protocols for scalable query processing, and an indexing protocol for ecient routing for spatial queries. The data against which network search is performed is maintained in local real-time databases close to the data sources. The design follows a bottom-up approach in the sense that the topology for query routing is constructed from the underlying network topology. We have built a prototype of the system on a cloud testbed and developed applications that use network search functionality. Testbed measurements suggest that it is feasible to engineer a network search system that processes queries at low latency and low overhead and that can scale to 100'000 nodes. Simulation results for spatial queries show that query processing achieves response times and incurs overhead close to an optimal protocol, and that query result remains accurate under signicant churn.

Place, publisher, year, edition, pages
Stockholm: Kungliga Tekniska högskolan, 2016. 122 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2016:012
National Category
Communication Systems Telecommunications
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-184236 (URN)978-91-7595-858-3 (ISBN)
Public defence
2016-05-03, F3, Lindstedtsvägen 26, våningsplan 2, Sing-Sing, KTH Campus, Stockholm, 09:30 (English)
Opponent
Supervisors
Note

QC 20160411

Available from: 2016-04-11 Created: 2016-03-31 Last updated: 2017-08-16Bibliographically approved

Open Access in DiVA

fulltext(911 kB)23 downloads
File information
File name FULLTEXT01.pdfFile size 911 kBChecksum SHA-512
d8b5ed24181d524b81b5714cd3d10b9da72cea45faab453fe394e56a97177e46351cf2fb9787c361592428c56b3fcbab327ffccba84b8c03783d4999d4a07ee4
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Uddin, MisbahStadler, Rolf
By organisation
Communication NetworksACCESS Linnaeus Centre
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 79 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