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
A Bottom-Up Approach to Real-Time Search in Large Networks and Clouds
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.ORCID iD: 0000-0001-5872-7809
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: urn:nbn:se:kth:diva-184236ISBN: 978-91-7595-858-3 (print)OAI: oai:DiVA.org:kth-184236DiVA: diva2:915752
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
List of papers
1. Graph search for cloud network management
Open this publication in new window or tab >>Graph search for cloud network management
2014 (English)In: IEEE/IFIP NOMS 2014 - IEEE/IFIP Network Operations and Management Symposium: Management in a Software Defined World, IEEE conference proceedings, 2014Conference paper, Published paper (Refereed)
Abstract [en]

A large part of operational and configuration information in networks and clouds has graph structure, e.g., virtual network topologies, IP flows, communication links of distributed cloud applications. The final objective of this work is to develop a scalable management system that allows real-time management applications, such as network analytics and anomaly detection applications, to search for graph-structured operational information. The paper contains a step towards this objective. The key challenge is to devise an efficient and scalable search process on data that is volatile and distributed across the network infrastructure. Approaches that are currently pursued for distributed graph databases are not applicable in this context. This paper presents design options and possible solutions for engineering a scalable graph search system that supports management applications. It includes a simple information model based on property graphs and a search query language based on keyword search. The architecture of the system centers around a distributed search plane that performs query processing using a network of search nodes. Finally, the paper outlines the design of a search node, which contains a local database that maintains graph partitions.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2014
Keyword
distributed management, distributed query processing, graph search, in-network management, network search, Electric network topology, Network management, Query languages, Query processing, Search engines, Information management
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-167623 (URN)10.1109/NOMS.2014.6838335 (DOI)000356862300105 ()2-s2.0-84904150733 (Scopus ID)9781479909131 (ISBN)
Conference
IEEE/IFIP Network Operations and Management Symposium: Management in a Software Defined World, NOMS 2014, 5 May 2014 - 9 May 2014, Krakow
Note

QC 20150525

Available from: 2015-05-25 Created: 2015-05-22 Last updated: 2016-04-11Bibliographically approved
2. Scalable Matching and Ranking for Network Search
Open this publication in new window or tab >>Scalable Matching and Ranking for Network Search
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
Keyword
distributed management, distributed query processing, innetwork management, matching and ranking, Network search
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-128191 (URN)10.1109/CNSM.2013.6727844 (DOI)000345853200042 ()2-s2.0-84894467062 (Scopus ID)978-3-901882-53-1 (ISBN)
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
3. A Query Language for Network Search
Open this publication in new window or tab >>A Query Language for Network Search
2013 (English)In: Proceedings of the 2013 IFIP/IEEE International Symposium on Integrated Network Management, IM 2013, New York: IEEE conference proceedings, 2013, 109-117 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. This paper presents a query language for network search and discusses how search queries can be executed in a networked system. The search space consists of named objects that are modeled as sets of attribute-value pairs. The data model is more general than the relational model, and the query language is more expressive than relational calculus. The paper shows that distributed query processing can be performed using an echo algorithm and that name resolution can be embedded in query processing. Finally, two use cases for network search are presented, one in networking and one in cloud computing, the latter backed up by a prototype implementation.

Place, publisher, year, edition, pages
New York: IEEE conference proceedings, 2013
Keyword
Network search, management paradigms, distributed management, name resolution
National Category
Computer Systems Communication Systems
Identifiers
urn:nbn:se:kth:diva-102881 (URN)000327159900014 ()2-s2.0-84883472607 (Scopus ID)978-1-4673-5229-1 (ISBN)
Conference
Integrated Network Management (IM 2013), 2013 IFIP/IEEE International Symposium on; Date 27-31 May 2013, Ghent, Belgium
Note

QC 20130809

Available from: 2012-09-27 Created: 2012-09-27 Last updated: 2016-04-11Bibliographically approved
4. 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)In: Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium, IEEE conference proceedings, 2016, 985-990 p.Conference paper, Published paper (Refereed)
Abstract [en]

Networked systems, such as telecom networks and cloud infrastructures, generate and hold vast amounts of configuration 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, an echo protocols for scalable query processing, and an indexing protocol for efficient 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 it remains accurate under significant churn.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2016
Keyword
bottom-up design, cloud management, distributed query processing, network management, network search, real-time management, Indexing (materials working), Network architecture, Query languages, Query processing, Safety devices, Software prototyping, Testbeds, Topology, Cloud managements, Information management
National Category
Computer Engineering
Identifiers
urn:nbn:se:kth:diva-197200 (URN)10.1109/NOMS.2016.7502937 (DOI)000389830100148 ()2-s2.0-84979787316 (Scopus ID)9781509002238 (ISBN)
Conference
2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016, 25 April 2016 through 29 April 2016
Note

QC 20161212

Available from: 2016-12-12 Created: 2016-11-30 Last updated: 2017-01-24Bibliographically approved
5. Spatial Search in Networked Systems
Open this publication in new window or tab >>Spatial Search in Networked Systems
2015 (English)In: 2015 11TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM), IEEE conference proceedings, 2015, 327-335 p.Conference paper, Published paper (Refereed)
Abstract [en]

Information in networked systems often has spatial properties: routers, sensors, or virtual machines have coordinates. in a geographical or virtual space, for instance. In this paper, we propose a peer-to-peer design for a spatial search system that processes queries, such as range or nearest-neighbor queries, on spatial information cached on nodes inside a networked system. Key to our design is a protocol that creates a distributed index of object locations and adapts to object and node churn. The indexbuilds upon the concept of the minimum bounding rectangle, to efficiently encode a large set of locations. We present a search protocol, which is based on an echo protocol and performs query routing. Simulations show the efficiency of the protocol in pruning the search space, thereby reducing the protocol overhead. For many queries, the protocol efficiency increases with the network size and approaches that of an optimal protocol for large systems. The protocol overhead depends on the network topology and is lower if neighboring nodes are spatially close. As a key difference to works in spatial databases, our design is bottom-up, which makes query routing network-aware and thus efficient in networked systems.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2015
Series
International Conference on Network and Service Management, ISSN 2165-9605
Keyword
network search, spatial search, distributed spatial index, distributed query processing
National Category
Engineering and Technology Telecommunications
Research subject
Computer Science; Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-181035 (URN)10.1109/CNSM.2015.7367378 (DOI)000379333700048 ()2-s2.0-84964043453 (Scopus ID)
Conference
11th International Conference on Network and service management (CNSM), Barcelona, Spain, November 9-13, 2015.
Note

QC 20160228

Available from: 2016-01-27 Created: 2016-01-27 Last updated: 2016-08-12Bibliographically approved
6. Management by Network Search
Open this publication in new window or tab >>Management by Network Search
2012 (English)In: Proceedings of the 2012 IEEE Network Operations and Management Symposium, NOMS 2012, New York: IEEE Communications Society, 2012, 146-154 p.Conference paper, Published paper (Refereed)
Abstract [en]

While networked systems hold and generate vast amounts of configuration and operational data, this data is not accessible through a simple, uniform mechanism. Rather, it must be gathered using a range of different protocols and interfaces. Our vision is to make all this data available in a simple format through a realtime search process which runs within the network and aggregates the data into a form needed by applications - a concept we call network search. We believe that such an approach, though challenging, is technically feasible and will enable rapid development of new management applications and advanced network functions. This paper motivates and formulates the concept of network search, compares it to related concepts like web search, outlines a search architecture, describes the design space and research challenges, and reports on a testbed implementation with management applications built for exploratory purposes of this new paradigm.

Place, publisher, year, edition, pages
New York: IEEE Communications Society, 2012
Series
IEEE IFIP Network Operations and Management Symposium, ISSN 1542-1201
Keyword
Advanced networks, Design spaces, Different protocols, Management applications, Network search, Networked systems, Operational data, Real time, Research challenges, Search architecture, Search process, Web searches
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-86144 (URN)10.1109/NOMS.2012.6211893 (DOI)000309517000018 ()2-s2.0-84864250287 (Scopus ID)978-146730268-5 (ISBN)
Conference
IEEE Network Operations and Management Symposium, NOMS 2012; Maui, HI; 16 April 2012 through 20 April 2012
Funder
ICT - The Next Generation
Note

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

QC 20120604

Available from: 2012-06-04 Created: 2012-02-13 Last updated: 2016-04-11Bibliographically approved
7. Real-Time Search in Clouds
Open this publication in new window or tab >>Real-Time Search in Clouds
2013 (English)In: Proceedings of the 2013 IFIP/IEEE International Symposium on Integrated Network Management, IM 2013, New York: IEEE , 2013, 1070-1071 p.Conference paper, Published paper (Refereed)
Abstract [en]

We developed a novel approach for management of networks/networked systems based on network search [4]. Network search provides a simple, uniform interface, through which human administrators and management applications can obtain network information, configuration or operational, without knowing its schema and location. We believe that the capability of network search will spur the development of new tools for human administrators and enable the rapid development of new classes of network control functions and applications.

Place, publisher, year, edition, pages
New York: IEEE, 2013
Keyword
Management applications, Network control, Network information, Network search, Real-time searches, Uniform interface
National Category
Telecommunications
Identifiers
urn:nbn:se:kth:diva-128192 (URN)000327159900169 ()2-s2.0-84883481353 (Scopus ID)978-1-4673-5229-1 (ISBN)
Conference
Demonstration Track, In Proc. IEEE/IFIP International Symposium on Integrated Network Management (IM), Ghent, Belgium, May 27-30, 2013.
Note

QC 20130930

Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2016-04-11Bibliographically approved
8. A Bottom-Up Design for Spatial Search in Large Networks and Clouds
Open this publication in new window or tab >>A Bottom-Up Design for Spatial Search in Large Networks and Clouds
2016 (English)Report (Other academic)
Abstract [en]

Information in networked systems often has spatial semantics: routers, sensors, or virtual machines have coordinates in a geographical or virtual space, for instance. In this paper, we propose a design for a spatial search system that processes queries against spatial information which is maintained in local databases inside a large networked system. In contrast to previous works in spatial databases and peer-to-peer designs, our design is bottom-up, which makes query routing network-aware and thus efficient, and which facilitates system bootstrapping and adaptation. Key to our design is a protocol that creates and maintains a distributed index of object locations based on information from local databases and the underlying network topology. The index builds upon minimum bounding rectangles (MBRs) to efficiently encode locations. We present a generic search protocol which is based on an echo protocol and uses the index to prune the search space and perform query routing. The response times of search queries increase with the diameter of the network, which is asymptotically optimal. We study the performance of the protocol through simulation in static and dynamic network environments, for different network topologies, and for network sizes upto 100'000 nodes. In all experiments, the overhead incurred by our protocol lies within thirty percent of a hypothetical optimal protocol. In addition, the protocol provides high accuracy under significant churn.

Keyword
network search, spatial search, spatial index, distributed query processing, bottom-up design
National Category
Communication Systems Telecommunications
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-181037 (URN)
Note

NQC 20160228

Available from: 2016-01-27 Created: 2016-01-27 Last updated: 2017-01-24Bibliographically approved

Open Access in DiVA

fulltext(3085 kB)413 downloads
File information
File name FULLTEXT01.pdfFile size 3085 kBChecksum SHA-512
cd870b5f94ceda11987d67750cd50cfdac8deee20e906dda1c0317497bef62e0b4242b8c505bfa5a373c0f0485fda7213941f1f0d4c36a985854130d032017d8
Type fulltextMimetype application/pdf

Authority records BETA

Uddin, Misbah

Search in DiVA

By author/editor
Uddin, Misbah
By organisation
ACCESS Linnaeus CentreCommunication Networks
Communication SystemsTelecommunications

Search outside of DiVA

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

isbn
urn-nbn

Altmetric score

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