• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
home
vision user
search
Advanced search
Priority areas
by year

News

8 September 2017

The Philosophy of Foucault, and Social Media Attitudes across Global School Settings

One of the chapters in Springer’s newly released academic volume Transforming Education is co-authored by IOE education innovation researcher Diana Koroleva. Entitled Coup D’etat in the Panopticon: Social Networking in Education, the paper has been inspired by a series of seminars in philosophy Diana was attending on her doctoral track at the IOE Graduate School of Education.

11 August 2017

HSE Book Series Published by Springer

Springer, one of the world's leading publishers of scientific literature, has launched a new book series, entitled ‘Societies and political orders in transition’. The series has been initiated by the HSE Faculty of Social Sciences, and three HSE representatives are members of the series International Advisory Board, with the other four members coming from universities in Germany, UK and the USA.

14 July 2017

Universities as Innovation Drivers

The latest issue of the Foresight Journal (vol. 11. No. 2), published as a special issue, looks at various aspects of integrating universities’ educational, research, and innovative activities in a ‘knowledge triangle.’ Experts from Austria, Indonesia, Iran, Russia, Sweden, and the UK, as well as representatives of the OECD had the opportunity to share their knowledge in this field.

Book chapter

Shared Memory Buffer Management for Heterogeneous Packet Processing

P. 471-480.
Nikolenko S. I., Kogan K., Eugster P., Sirotkin A.

Packet processing increasingly involves heterogeneous requirements. We consider the well-known model of a shared memory switch with bounded-size buffer and generalize it in two directions. First, we consider unit-sized packets labeled with an output port and a processing requirement (i.e., packets with heterogeneous processing), maximizing the number of transmitted packets. We analyze the performance of buffer management policies under various characteristics via competitive analysis that provides uniform guarantees across traffic patterns (Borodin and El-Yaniv, 1998). We propose the Longest-Work-Drop policy and show that it is at most 2-competitive and at least sqrt 2}-competitive. Second, we consider another generalization, posed as an open problem in [10], where each unit-sized packet is labeled with an output port and intrinsic value, and the goal is to maximize the total value of transmitted packets. We show first results in this direction and define a scheduling policy that, as we conjecture, may achieve constant competitive ratio. We also present a comprehensive simulation study that validates our results.

Language: English
 Full text (PDF, 3.02 Mb)
 Text on another site
Keywords: schedulingshared memory

In book

Proceedings of the IEEE 34th International Conference on Distributed Computing Systems (ICDCS 2014)
NY: IEEE Press, 2014.
Similar publications
Understanding the Fundamentals of the U.S. Presidential Election System
Belenky A. Heidelberg; NY; Dordrecht; L.: Springer, 2012.

This is the first book on the U.S. presidential election system to analyze the basic principles underlying the design of the existing system and those at the heart of competing proposals for improving the system. The book discusses how the use of some election rules embedded in the U.S. Constitution and in the Presidential Succession Act may cause skewed or weird election outcomes and election stalemates. The book argues that the act may not cover some rare though possible situations which the Twentieth Amendment authorizes Congress to address. Also, the book questions the constitutionality of the National Popular Vote Plan to introduce a direct popular presidential election de facto, without amending the Constitution, and addresses the plan’s “Achilles’ Heel.”  In particular, the book shows that the plan may violate the Equal Protection Clause from the Fourteenth Amendment of the Constitution. Numerical examples are provided to show that the counterintuitive claims of the NPV originators and proponents that the plan will encourage presidential candidates to “chase” every vote in every state do not have any grounds. Finally, the book proposes a plan for improving the election system by combining at the national level the “one state, one vote” principle – embedded in the Constitution – and the “one person, one vote” principle. Under this plan no state loses its current Electoral College benefits while all the states gain more attention of presidential candidates.

Added: Sep 25, 2012
Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times
Lazarev A. A., Arkhipov D. I., Werner F. Otto-von-Guericke University Magdeburg, Germany. Institut fur Mathematische Optimierung, 2015. No. 11.
The following special case of the classical NP-hard scheduling problem 1jrj jLmax is considered. There is a set of jobs N = f1; 2; : : : ; ng with identical processing times pj = p for all jobs j 2 N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1jrj jCmax, presented by Garey et al. (1981) and Simons (1978) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q _ n log n) and O(n2 log n), respectively, where 10􀀀Q is the accuracy of the input-output parameters.
Added: Apr 10, 2015
Monographs of System Dependability. Dependability of Networks
Vol. 2. Wrocław: Oficyna Wydawnicza Politechnki Wroclawskiej, 2010.

This chapter describes an economic model for independent job flow management in distributed computing environments with non-dedicated resources. The model is based on the concept of fair resource distribution between users and owners of computational nodes by means of economic mechanisms in a virtual organization. Scheduling is performed in cycles in accordance with dynamically updated schedules on local processor nodes. Schedule optimization is performed using dynamic programming methods using the set of criteria in accordance with the economic policy of the virtual organization.

Added: Apr 20, 2012
Parallel hybrid heuristics for the permutation flow shop problem
Pardalos P. M., Ravetti M., Riveros C. et al. Annals of Operations Research. 2012. Vol. 199. No. 1. P. 269-284.
This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by Fm{pipe}prmu{pipe}C max. In the permutational scenario, the sequence of jobs has to remain the same in all machines. The Flowshop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for medium and large scale instances, high-quality heuristics are needed to find good solutions in reasonable time. We propose and analyse parallel hybrid search methods that fully use the computational power of current multi-core machines. The parallel methods combine a memetic algorithm (MA) and several iterated greedy algorithms (IG) running concurrently. Two test scenarios were included, with short and long CPU times. The tests were conducted on the set of benchmark instances introduced by Taillard (Eur. J. Oper. Res. 64:278-285, 1993), commonly used to assess the performance of new methods. Results indicate that the use of the MA to manage a pool of solutions is highly effective, allowing the improvement of the best known upper bound for one of the instances.
Added: Feb 5, 2013
Economic Models of Scheduling in Distributed Systems
Toporkov V. V., Toporkova A. S., Tselishev A. et al. In bk.: Monographs of System Dependability. Dependability of Networks. Vol. 2. Wrocław: Oficyna Wydawnicza Politechnki Wroclawskiej, 2010. Ch. 10. P. 143-154.

This chapter describes an economic model for independent job flow management in distributed computing environments with non-dedicated resources. The model is based on the concept of fair resource distribution between users and owners of computational nodes by means of economic mechanisms in a virtual organization. Scheduling is performed in cycles in accordance with dynamically updated schedules on local processor nodes. Schedule optimization is performed using dynamic programming methods using the set of criteria in accordance with the economic policy of the virtual organization.

Added: Apr 20, 2012
Resource Co-allocation Algorithms for Job Batch Scheduling in Dependable Distributed Computing
Toporkov V. V., Toporkova A. S., Yemelyanov D. M. et al. In bk.: Dependable Computer Systems. Vol. 97. Berlin; Heidelberg: Springer, 2011. P. 243-256.

This work presents slot selection algorithms in economic models for independent job batch scheduling in distributed computing with non-dedicated resources. Existing approaches towards resource co-allocation and multiprocessor job scheduling in economic models of distributed computing are based on search of time-slots in resource occupancy schedules. The sought time-slots must match requirements of necessary span, computational resource properties, and cost. Usually such scheduling methods consider only suited variant of time-slot set. This work discloses a scheduling scheme that features multi-variant search. Two algorithms of linear complexity for search of alternative variants are proposed and compared. Having several optional resource configurations for each job makes an opportunity to perform an optimization of execution of the whole batch of jobs and to increase overall efficiency of scheduling.

Added: Apr 20, 2012
Resource Selection Algorithms for Economic Scheduling in Distributed Systems
Toporkov V. V., Toporkova A. S., Bobchenkov A. V. et al. Procedia Computer Science. 2011. No. 4. P. 2267-2276.

In this paper presented slot selection algorithms in economic model for independent job batch scheduling in a distributed computing with non-dedicated resources. Exiting approaches towards resource co-allocation and multiprocessor job scheduling in economic models of distributed computing are based on search of time-slots in resource occupancy schedules. The sought time-slots must match requirements of necessary span, computational resource properties, and cost. Usually such scheduling methods consider only one suited variant of time-slot set. This paper discloses a scheduling scheme that features multi-variant search. Two algorithms of linear complexity for search of alternative variants are compared. Having several optional resource configurations for each job makes an opportunity to perform an optimization of execution of the whole bath of jobs and to increase overall efficiency of scheduling.

Added: Apr 13, 2012
Proceedings of the Second ACM SIGCOMM workshop on Hot topics in Software Defined Networking (HotSDN-2013)
Edited by: N. Foster, R. Sherwood. NY: ACM Press, 2013.
Added: Sep 24, 2013
Resource co-allocation algorithms in distributed job batch scheduling
Toporkov V. V., Toporkova A. S., Bobchenkov A. V. et al. In bk.: Advances in Information Technology from AI to Virtual Reality. Amman: UbiCC Publisher, 2011. P. 2-20.

In this work, we present slot selection algorithms for job batch scheduling in distributed computing with non-dedicated resources. Jobs are parallel applications and these applications are independent. Existing approaches towards resource co-allocation and parallel job scheduling in economic models of distributed computing are based on search of time-slots in resource occupancy schedules. The sought time-slots must match requirements of necessary span, computational resource properties, and cost. Usually such scheduling methods consider only one suited variant of time-slot set. This work discloses a scheduling scheme that features multi-variant search. Two algorithms of linear complexity for search of alternative variants are proposed. Having several optional resource configurations for each job makes an opportunity to perform an optimization of execution of the whole batch of jobs and to increase overall efficiency of scheduling.

Added: Apr 12, 2012
Метод эффективного планирования обслуживания с применением теории графов
Сидоренко В. Г., Филипченко К. М. Информатизация образования и науки. 2015. Т. 28. № 4. С. 123-132.

In this article some questions of technical systems scheduling and maintenance are considered on example vehicles. From one side, the scheduling has to satisfy the requirements of safety and be the effective for equability criterion, from another side. The mathematical apparatus, used in the article, bases on the combinatory and graph theory.

Added: Oct 21, 2015