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

Claim 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 1 ), 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 2 ), 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 1 ) being D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0 wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being a time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 being a time for transmitting requested multimedia information.

Claim 2

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 1 ), 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 2 ), 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 1 ) being D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0 wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being a time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 being a time for transmitting requested multimedia information.

Claim 4

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 1 ); 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 2 ) being D.sub.2 =t.sub.1 +RT/R.sub.0 wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 being the time for transmitting requested multimedia information.

Claim 5

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 1 ); 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 2 ) being D.sub.2 =t.sub.1 +RT/R.sub.0 wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 being the time for transmitting requested multimedia information.

Claim 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 second set with a second end of transmission time (t 2 ); 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 1 ); 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 1 ) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0 and wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 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.

Claim 7

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 2 ); 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 1 ); 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 1 ) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being D.sub.1 =|t.sub.1 -t.sub.2 |+RT/R.sub.0 and wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 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.

Claim 9

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 1 ); 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 2 ) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being D.sub.2 =t.sub.1 +RT/R.sub.0 and wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 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.

Claim 10

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 1 ); 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 2 ) which minimizes idle time at nodes of said second set and missed response times of requests, said distance function being D.sub.2 =t.sub.1 +RT/R.sub.0 and wherein R.sub.0 =T.sub.0 /t.sub.0, T 0 being the time for servicing each request to prevent the requesting subscriber from being without multimedia information and t 0 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.