[go: up one dir, main page]

WO2006002662A1 - Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples - Google Patents

Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples Download PDF

Info

Publication number
WO2006002662A1
WO2006002662A1 PCT/EP2004/007088 EP2004007088W WO2006002662A1 WO 2006002662 A1 WO2006002662 A1 WO 2006002662A1 EP 2004007088 W EP2004007088 W EP 2004007088W WO 2006002662 A1 WO2006002662 A1 WO 2006002662A1
Authority
WO
WIPO (PCT)
Prior art keywords
processing
data
scheduling
data portion
scheduled
Prior art date
Application number
PCT/EP2004/007088
Other languages
English (en)
Inventor
Andras Vajda
Arto Juhani Mahkonen
Thomas Wennberg
Original Assignee
Telefonaktiebolaget Lm Ericsson (Publ)
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Telefonaktiebolaget Lm Ericsson (Publ) filed Critical Telefonaktiebolaget Lm Ericsson (Publ)
Priority to PCT/EP2004/007088 priority Critical patent/WO2006002662A1/fr
Publication of WO2006002662A1 publication Critical patent/WO2006002662A1/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/50—Network services
    • H04L67/60—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources
    • H04L67/61—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources taking into account QoS or priority requirements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/50—Network services
    • H04L67/60—Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources
    • H04L67/62—Establishing a time schedule for servicing the requests

Definitions

  • the invention relates to a method and a device for scheduling processing of data portions from multiple data sources by a commonly utilized processing unit
  • different processing tasks can be e.g. tasks related to different channels or different kinds of tasks such as source or channel encoding or decoding, echo canceling, tone sending or the like.
  • Data to be processed by a processing unit may be provided as data portions such as data packets or frames.
  • data portions such as data packets or frames.
  • Known kinds data of portions are e.g. an IP (internet protocol) packet, an SDU (service data unit), an ATM (asynchronous transfer mode) frame or an Iu- frame.
  • asynchronous scheduling data portions are stored in a FIFO (first in - first out) buffer common to multiple data sources and the data portions are processed in the order in which they have been received in the common FIFO buffer.
  • Data portions from a particular one of the data sources are not received at exactly periodically repeated arrival times but are subject to an arrival jitter.
  • the order at which the data portions are received in the FIFO buffer may vary.
  • the further buffer causes a further buffering delay in addition to the buffering delay of the FIFO buffer.
  • a method for scheduling processing data portions from a plurality of data sources by a commonly utilized processing device may relate to a plurality of transmission channels, i.e. each of said plurality of data sources may relate to a respective transmission channel.
  • the invented method comprises the steps of:
  • scheduling processing of a data portion with a scheduled processing start time closest to the reference time may be performed by detecting that processing the current data portion has been completed.
  • the proposed method for scheduling data portions may be utilized if the number of data sources is changed or reconfigured.
  • the reference time may be determined according to a scheduled processing start time of the current data portion. By this the assignment of a scheduled a processing start time does not need to be synchronized with other devices.
  • the reference time may be determined using a clocking device.
  • processing of data portions from a higher prioritised data source may be prioritised as regards to processing of data portions from a lower prioritised data source.
  • this data sources may be related to a respective quality of service class and a requirement on a quality of service may be complied with.
  • a scheduled processing start time for a data portion from a particular data source is determined using a scheduled processing start time of a previously scheduled data portion from the particular data source and a repetition interval for the particular data source.
  • this data portions may be scheduled to be processed at a constant rate. By this a jitter of times at which processed data portions are available may also be minimized.
  • a scheduling device for scheduling processing data portions from a plurality of data sources by a commonly utilized processing device.
  • the scheduling device comprises:
  • a data portion queue for temporarily storing the data portions to be processed by the processing device - an assignment unit for assigning to a data portion received from a data source a scheduled processing start time
  • Detecting that processing capacity is available for processing a next data portion may be performed by detecting that processing the current data portion has been completed.
  • the timing unit may be adapted to determine the reference time according to a scheduled processing start time of the current data portion. By this the assignment of a scheduled processing start time does not need to be synchronized with other devices.
  • the timing unit may be adapted to determine the reference time using a clocking device.
  • the scheduling unit may be adapted to prioritise processing of data portions from a higher prioritised data source as regards to processing of data portions from a lower prioritised data source.
  • this data sources may be related to a respective quality of service class and requirements to a quality of service class may be complied with.
  • the assignment unit may be adapted to assign a scheduled processing start time for a data portion from a particular data source according to a scheduled processing start time of a previously scheduled data portion from the particular data source and a repetition interval for the particular data source.
  • This data portions may be scheduled to be processed at a constant rate. By this a jitter of times at which processed data portions are available may also be minimized.
  • Figure 1 depicts a plurality of units that are used for the processing of data portions according to the invention.
  • Figure 2 depicts a scheduling device according to the invention.
  • FIG. 3 depicts a sequence of processing steps to be performed when embodying the invention.
  • Figure 1 depicts a plurality of units that are used for the processing of data portions according to the invention.
  • the embodiment of figure 1 comprises n data sources Cl, C2 ... Cn of which a first, a second and an nth data source Cl, C2, and Cn are depicted.
  • the first to nth data source Cl, C2, ... Cn may each relate to a transmission channel, via which data portions are transmitted towards the processing unit PU, that is commonly utilized for the first to nth data source Cl, C2, ... Cn.
  • the first to nth data source Cl, C2 ... Cn may be data sources of different kind or data sources of the same kind.
  • the first to nth data source Cl, C2 ... Cn are repeatedly outputting data portions to be processed by the processing unit PU.
  • the data portions for a particular one of the first to nth data source Cl, C2 ... Cn may be data portions of different kind and the processing tasks to be performed on the data portions may be different kinds of processing tasks.
  • a respective software instance may be provided to be executed by the commonly utilized processing unit PU.
  • the data portions may be e.g. speech data portions comprising speech data or control data portions related to a speech channel and the processing tasks to be performed on the data portions may relate to a tone sending, an echo canceling, or an encoding, decoding or transcoding of speech data transmitted within said data portions.
  • the processing times for processing a data portion may be different for different data portions to be processed by the processing unit PU.
  • data portions to be processed by the processing unit PU are received from one of the first to nth data source C 1 , C2, ... Cn in a first buffer B 1 that is controlled by a control unit CU.
  • the first buffer may apply the FIFO (first in - first out) principle, i.e. the first buffer may be adapted to output the received data portions in the order in which they have been received in the first buffer Bl.
  • the control unit is adapted to assign to each of the data portions received from a particular one of the first to nth data source Cl, C2 ... Cn a respective scheduled processing start time.
  • the scheduled processing start time for a first data portion received after an initialisation phase of the processing device PU may be determined according to a current time and an initial delay.
  • the scheduled processing start time for a further data portion may be determined according to a scheduled processing start time of a previously scheduled data portion from the particular data source and a repetition interval assigned to the particular data source. Said repetition interval may be defined according to the type of the data source, e.g. 20 milliseconds for a UMTS speech channel.
  • the delivery time for a data portion from a particular channel may be calculated after the processing unit PU has executed a processing task for the particular channel.
  • the control unit CU controls the first buffer Bl and a second buffer B 2 to copy data portions from the first buffer B 1 to the second buffer B2.
  • the second buffer may be arranged such that the data portions stored in the second buffer are sorted according to the scheduled processing start time of the data portions. To that end the second buffer may be implemented as a linked list. By this scanning the second buffer B2 for a most urgent data portion may be avoided. Data portions in the second buffer B2 may be rescheduled when a data portion is copied from the first buffer B 1 to the second buffer B2.
  • the second buffer B2 may be a freely accessible memory and the control unit CU may hold a table assigning an indication of a data portion with the scheduled processing start time of that data portion.
  • data portions must be accessible from the second buffer B2 according to their indication kept in the control unit.
  • a reference time is determined. Said reference time may be determined using a clocking device. Furthermore said reference time may be determined according to a processing status of the processing device PD. E.g. the reference time may be determined when the processing device starts processing of a data portion. Alternatively the reference time may be determined when the processing device has completed processing a data portion. Alternatively the reference time may be determined according to a scheduled processing start time of a currently processed data portion.
  • the control unit CU schedules processing of a data portion with a scheduled processing start time closest to the reference time. I.e. if the scheduled processing start time of the current data portion has been used as reference time and the data portions are stored in the second buffer B 2 in the order of their respective scheduled processing start time, the data portions may be processed by the processing unit PU in the order in that they have been stored in the second buffer B2.
  • control unit CU may determine according to the list of scheduled processing starts the data portion with the scheduled processing start time closest to the reference time and initiate processing of this determined data portion by the processing unit.
  • the data portion to be processed next may be copied to the processing device and deleted from the second buffer B2.
  • the control unit CU may control the first buffer B 1 and the second buffer B2 such that available data portions are copied from the first buffer Bl to the second buffer B2.
  • Advantageously all available data portions are copied from the first buffer Bl to the second buffer B2.
  • a particular one of the first to nth data source Cl, C2 ... Cn may be prioritized compared to another one of the data sources. This may e.g. apply if transmission channels of a different quality of service classes are assigned to the first to nth data source Cl, C2 ... Cn.
  • the data portion scheduled to be processed next may be first determined within the data portions received from data sources with a high priority.
  • the scheduled processing start time of a highly prioritised data portion may be interpreted as a deadline for processing that data portion and processing of a previously scheduled data portion may be terminated when the deadline for processing the prioritised data portion is about to expire.
  • the reception of data portions from a particular data source may be supervised by the control unit CU.
  • Outputting data portions that have been processed by the processing device may be triggered by an output scheduler OS downstream to the processing unit PU.
  • the output scheduler OS may store processed data portions and output the processed data portions at previously scheduled delivery times. Delivery times may be determined from previous delivery times and a repetition interval that is common for a particular data sink towards that processed data portions are transmitted.
  • the first delivery time for a particular data source and a respective data sink may be determined according to a reception time of a first data portion received from the respective data source.
  • Determining the first delivery time for a data portion to be delivered towards the respective data sink may take into account an expected input jitter, a latency due to the scheduling process, and an expected processing time.
  • the first delivery time may be e.g. determined as the reception time of the first data portion increased by the sum of the input jitter, the expected latency due to the scheduling process and the expected processing time.
  • the input jitter relates to an expected jitter of reception times of data portions received from the particular data source.
  • the expected input jitter may be configured or determined from a measurement of an actual input jitter from the past.
  • the latency due to the scheduling process takes into account an expected delay due to data portions that are scheduled to be processed simultaneously. E.g. if a certain number of data portions have been scheduled to be processed simultaneously, the expected delay due to the simultaneous scheduling related to the sum of the processing times of the simultaneously scheduled data portions.
  • FIG. 2 depicts a scheduling device SD according to the invention.
  • the scheduling device SD may be implemented in hardware in software or in a combination thereof.
  • the scheduling device SD is provided for scheduling processing data portions from a first to nth data source DSl, DS2 ... DSn by a commonly utilized processing device PD, to which the scheduling device SD is connected to.
  • the first to nth data source DSl, DS2 ... DSn may e.g. relate each to a respective transmission channel via which the data portions are transmitted towards the processing device.
  • the scheduling device SD comprises a data portion queue DPQ connected to the first to nth data source DSl, DS2 ... DSn for receiving data portions from the first to nth data source for DSl, DS2 ... DSn.
  • the data portion queue DPQ is provided for temporarily storing the data portions received from the first to nth data source for DSl, DS2 ... DSn.
  • the scheduling device SD further comprises an assignment unit AU, a timing unit TU, a scheduling unit SDU and a supervision unit SVU, all of them interconnected among each other and connected to the data portion queue DPQ.
  • the supervision unit SVU is further connected to the processing device PD for supervising the processing device PD.
  • the assignment unit AU is adapted to assign to each data portion received from the first to nth data source for DSl, DS2 ... DSn a respective scheduled processing start time. To that end the assignment unit AU may be adapted to assign a scheduled processing start time for a data portion from a particular data source according to a scheduled processing start time of a previously scheduled data portion from the particular data source and a repetition interval for the particular data source.
  • the scheduling unit SDU is adapted to schedule processing of a current data portion to be processed. This may be provided in that the scheduling unit SU selects within the data portions stored in the data portion queue that data portion the current data portion to be processed next.
  • the timing unit TU is adapted to determine a reference time. To that end the timing unit TU may be adapted to determine the reference time according to a scheduled processing start time of the current data portion or the timing unit TU may be adapted to determine the reference time using a clocking device.
  • the clocking device may be a device external to the timing unit or be comprised in the timing unit TU.
  • the scheduling device SD further comprises a supervising unit SVU for detecting that processing capacity is available for processing a next data portion. This may be achieved in that the scheduling device detects that processing the current data portion has been completed. To that end the supervision unit SVU may be adapted to receive from the processing device a signal indicating that processing the current data portion has been completed.
  • the scheduling unit SDU is adapted to schedule processing of a data portion with a scheduled processing start time closest to the reference time when processing capacity is available for processing a next data portion. This may be performed upon detecting that processing the current data portion has been completed.
  • the scheduling unit SDU may be adapted to prioritise processing of data portions from a higher prioritised data source as regards to processing of data portions from a lower prioritised data source.
  • FIG. 3 depicts a sequence of method steps that may be performed when carrying out the invention.
  • the depicted method is provided for scheduling processing data portions from a plurality of data sources by a commonly utilized processing device.
  • a processing start time is assigned to data portions received from the data sources, wherein the processing start time indicates when processing the respective data portion is scheduled.
  • a current data portion is scheduled.
  • a reference time is determined. The reference time may be determined according to a scheduled processing start time of the current data portion or the reference time may be determined using a clocking device.
  • a fourth step S4 it is detected that processing capacity is available for processing a next data portion. This may be performed in that it is detected that processing the current data portion has been completed. According to the fourth step S4, i.e. when processing capacity is available for processing a next data portion processing of a data portion with a scheduled processing start time closest to the reference time is scheduled in a fifth step S5.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

La présente invention concerne un procédé permettant de programmer le traitement de parties de données d'une pluralité de sources de données par un dispositif de traitement utilisé en commun, ce procédé consistant: à assigner (S1) à une partie de données reçues d'une source de données une heure de début de traitement programmée, à programmer (S2) le traitement d'une partie de données courantes, à déterminer (S3) un temps de référence, lorsqu'une capacité de traitement disponible pour traiter une partie de données suivante (S4), à programmer (S5) le traitement d'une partie de données avec une heure de début de traitement programmée qui est la plus proche du temps de référence.
PCT/EP2004/007088 2004-06-30 2004-06-30 Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples WO2006002662A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/EP2004/007088 WO2006002662A1 (fr) 2004-06-30 2004-06-30 Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/EP2004/007088 WO2006002662A1 (fr) 2004-06-30 2004-06-30 Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples

Publications (1)

Publication Number Publication Date
WO2006002662A1 true WO2006002662A1 (fr) 2006-01-12

Family

ID=34958017

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2004/007088 WO2006002662A1 (fr) 2004-06-30 2004-06-30 Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples

Country Status (1)

Country Link
WO (1) WO2006002662A1 (fr)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1999029108A1 (fr) * 1997-12-04 1999-06-10 Gte Laboratories Incorporated Procede et systeme de video presque sur demande
US6088722A (en) * 1994-11-29 2000-07-11 Herz; Frederick System and method for scheduling broadcast of and access to video programs and other data using customer profiles

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6088722A (en) * 1994-11-29 2000-07-11 Herz; Frederick System and method for scheduling broadcast of and access to video programs and other data using customer profiles
WO1999029108A1 (fr) * 1997-12-04 1999-06-10 Gte Laboratories Incorporated Procede et systeme de video presque sur demande

Similar Documents

Publication Publication Date Title
EP0734195B1 (fr) Système de réduction de délai avec garantie de bande passante pour trafic en temps réel
EP1137226B1 (fr) Amélioration de l'ordonnancement de paquets véhivulant des informations en temps réel sur un réseau par paquets
US20070076766A1 (en) System And Method For A Guaranteed Delay Jitter Bound When Scheduling Bandwidth Grants For Voice Calls Via A Cable Network
KR20170118793A (ko) 네트워크에 있어서의 데이터 프레임의 트래픽 쉐이핑의 방법 및 그 디바이스 및 컴퓨터 프로그램
CA2340369A1 (fr) Commutation de couche une dans un reseau base sur des paquets, des cellules ou des blocs
WO1990011659A1 (fr) Reseau de communications par paquets exempt d'encombrements
JPH10200549A (ja) セルスケジューリング装置
JP2001519120A (ja) 階層型パケット・スケジューリング方法及び装置
WO2002073865A2 (fr) Systeme d'ordonnancement et de tri temporel de paquets
CN1256063A (zh) 一种分组交换数据传输方法
US7142551B2 (en) Hardware implementation of Voice-over-IP playback with support for comfort noise insertion
US6882625B2 (en) Method for scheduling packetized data traffic
US7817643B2 (en) System and method for varying the scheduling of real time protocol (RTP) packets
EP2323317A1 (fr) Procédé de commande de bande et dispositif de commande de bande pour dispositif de n ud
EP1461920A1 (fr) Procede d'admission et de programmation de trafic de reseau en temps reel
EP1471694B1 (fr) Procédé de dimensionnement d'un largeur de bande dans réseaux de voix-sur-IP
US10530519B2 (en) System and method for packet scheduling
WO2006002662A1 (fr) Procede et appareil de programmation de traitement de parties de donnees de source de donnees multiples
EP1330900B1 (fr) Procede et appareil pour le traitement de donnees asynchrones
KR20060125091A (ko) 슈퍼 프레임의 시작을 엄격히 지키는 레지덴셜 이더넷 노드장치 및 그 프레임 처리 방법
WO2012116761A1 (fr) Planification pour paquets sensibles au retard
Jabbour et al. SAF-PS: Starvation avoidance for priority scheduling
JP4302014B2 (ja) Ｅｔｈｅｒｎｅｔフレーム転送装置および方法
KR20020069994A (ko) 이동통신시스템의 패킷데이터 스케줄링 장치 및 방법
Ahmed et al. Switched Multi-hop Priority Queued Networks-Influence of priority levels on Soft Real-time Performance

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NA NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Country of ref document: DE

122 Ep: pct application non-entry in european phase