Scheduling transmission multimedia information in broadband networks using a token passing scheme

• US 5,555,378 A
• Filed: 03/02/1994
• Issued: 09/10/1996
• Est. Priority Date: 03/02/1994
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Gelman, Alexander, Halfin, Shlomo
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): STACHLER, ROBERT
• Application Number:
  US08/206,777
• Time in Patent Office: 923 Days
• Field of Search: 395/200, 395/200.13, 395/200.08, 395/849, 395/873, 395/477, 364/232.22
• US Class Current: 709/235
• CPC Class Codes: H04L 2012/5615 Network termination, e.g. NT1, NT2, PBX
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A scheduling system and method, which employ a token passing scheme, for scheduling transmission of multimedia information between information warehouses (IWHs) and CO clusters (CCs) interconnected by ATM switch(es). Each CO cluster employs a CC schedule processor, which has means for receiving and means for storing requests for multimedia information, means for sorting and prioritizing the requests, means for forwarding requests to appropriate IWHs, and means for accepting or rejecting tokens offered by IWHs in response to a request. The IWH employs an IWH schedule processor which includes means for receiving and means for storing requests from CO clusters, means for selecting a request and generating a token to be sent to the CO cluster originating the request, and means for storing a list of CO cluster rejecting tokens. Requests received from multiple subscribers are stored, sorted, and prioritized at CC schedule processors, which forward the requests to appropriate IWHs. The schedule processor of each IWH receives and stores requests from CO clusters, selects a request to be serviced based on a first distance function and issues a token to the CO cluster originating the selected request. The CC schedule processor of each CO cluster selects a token to be accepted based upon a second distance function, and the requested multimedia information is transmitted from the IWH issuing the token to the CO cluster. Other tokens are rejected and returned to the issuing IWH. Each IWH may maintain a list of CO cluster rejecting its issued tokens.

Claims

1. A system for scheduling transmission of multimedia information from a first set of nodes as requested by subscribers at a second set of nodes, wherein said first and second sets of nodes are interconnected by an ATM switch, such that collisions at said ATM switch are avoided and requests are serviced in a timely manner, said system comprising:

at each node of said first set, a first schedule processor which includes a first request processor connected to a first token processor, said first request processor receiving requests for multimedia information from nodes of said second set and said first token processor selecting a request from among said requests and issuing a token to the node of said second set which sent said selected request together with a first end of transmission time (t₁), and

at each node in said second set, a second schedule processor which includes a second request processor connected to a second token processor, said second request processor receiving requests for multimedia information from subscribers, wherein each of said received requests includes a response time (RT), and sending at least one of said received requests to one of said nodes of said first set together with a second end of transmission time (t₂), and said second token processor receiving tokens issued from said first token processors at nodes of said first set, selecting one of said tokens for acceptance, causing a message of acceptance to be sent to the node of said first set issuing said selected token, rejecting other of said tokens and returning said rejected tokens to nodes of said first set issuing said rejected tokens; and

wherein said first schedule processor further includes a return token store for holding a list of nodes of said second set rejecting tokens issued by said first token processor and means responsive to said list of nodes held at said return token store for performing a request selection using a distance function which minimizes idle time at said first schedule processor and missed response times of requests, said distance function (D₁) being

space="preserve" listing-type="equation">D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0

wherein

space="preserve" listing-type="equation">R.sub.0 =T.sub.0 /t.sub.0,

T₀ being a time for servicing each request to prevent the requesting subscriber from being without multimedia information and t₀ being a time for transmitting requested multimedia information.

2. The system of claim 1 for scheduling transmission of multimedia information, wherein said first and second schedule processors include first and second internal clocks, respectively, for tracking said first and second end-of-transmission times, t₁ and t₂, respectively, at said first and second request processors, respectively.

3. A system for scheduling transmission of multimedia information from a first set of nodes as requested by subscribers at a second set of nodes, wherein said first and second sets of nodes are interconnected by an ATM switch, such that collisions at said ATM switch are avoided and requests are serviced in a timely manner, said system comprising:

at each node of said first set, a first schedule processor which includes a first request processor connected to a first token processor, said first request processor receiving requests for multimedia information from nodes of said second set and said first token processor selecting a request from among said requests and issuing a token to the node of said second set which sent said selected request together with a first end of transmission time (t₁);

at each node in said second set, a second schedule processor which includes a second request processor connected to a second token processor, said second request processor receiving requests for multimedia information from subscribers, wherein each of said received requests includes a response time (RT), and sending at least one of said received requests to one of said nodes of said first set, and said second token processor receiving tokens issued from said first token processors at nodes of said first set, selecting one of said tokens for acceptance, causing a message of acceptance to be sent to the node of said first set issuing said selected token, and rejecting other of said tokens; and

wherein said second token processor performs token selection using a distance function which minimizes idle time at said second schedule processor and missed response times of requests, said distance function (D₂) being

space="preserve" listing-type="equation">D.sub.2 =t.sub.1 +RT/R.sub.0

wherein

space="preserve" listing-type="equation">R.sub.0 =T.sub.0 /t.sub.0,

T₀ being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t₀ being the time for transmitting requested multimedia information.

4. A method of scheduling transmission of multimedia information from a first set of nodes as requested by subscribers at a second set of nodes, wherein said first and second sets of nodes are interconnected by an ATM switch, such that collisions at said ATM switch are avoided and requests for multimedia information are serviced in a timely manner, said method comprising the steps of:

at each node of said second set,

receiving requests for multimedia information from subscribers, which requests each includes a response time (RT) and

sending at least one of said received requests to one of said nodes of said second set with a second end of transmission time (t₂); and

at each node of said first set,

receiving said requests for multimedia information sent from nodes of second set based on said RT of each request,

issuing a token to the node of said second set which sent said selected request, and

sending with said token a first end-of-transmission time (t₁); and

at each said node of said second set,

receiving tokens issued from nodes of said first set,

selecting one of said tokens for acceptance, said selecting including computing for each of said tokens a distance using a distance function (D₁) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being

space="preserve" listing-type="equation">D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0

and wherein

space="preserve" listing-type="equation">R.sub.0 =T.sub.0 /t.sub.0,

T₀ being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t₀ being the time for transmitting requested multimedia information; and

causing a message of acceptance to be sent to the node of said first set issuing said selected token.

5. The method of claim 4 of scheduling transmission of multimedia information further including the steps of

returning said rejected tokens from nodes of said second set to nodes of said first set issuing said rejected tokens and

holding at a return token store at nodes of said first set a list of nodes of said second set rejecting issued tokens.

6. A method of scheduling transmission of multimedia information from a first set of nodes as requested by subscribers at a second set of nodes, wherein said first and second sets of nodes are interconnected by an ATM switch, such that collisions at said ATM switch are avoided and requests for multimedia information are serviced in a timely manner, said method comprising the steps of:

at each node of said second set,

receiving requests for multimedia information from subscribers, which requests each includes a response time (RT) and

sending at least one of said received requests to one of said nodes of said first set; and

at each node of said first set,

receiving said requests for multimedia information sent from nodes of second set based on said RT of each request,

issuing a token to the node of said second set which sent said selected request, and

sending with said token a first end-of-transmission time (t₁); and

at each said node of said second set,

receiving tokens issued from nodes of said first set,

selecting one of said tokens for acceptance, said selecting including computing for each of said tokens a distance using a distance function (D₂) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being

space="preserve" listing-type="equation">D.sub.2 =t.sub.1 +RT/R.sub.0

and wherein

space="preserve" listing-type="equation">R.sub.0 =T.sub.0 /t.sub.0,

T₀ being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t₀ being the time for transmitting requested multimedia information; and

causing a message of acceptance to be sent to the node of said first set issuing said selected token.