Arbitration in multiprocessor communication node

• US 4,949,338 A
• Filed: 11/14/1988
• Issued: 08/14/1990
• Est. Priority Date: 04/06/1987
• Status: Expired due to Term

• Current Assignee: Nextiraone France (Nippon Telegraph and Telephone Corporation)
• Original Assignee: Racal Data Communications Incorporated
• Inventors: Albal, Nandakishore A., Goyal, Praduemn K.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/271,210
• Time in Patent Office: 638 Days
• Field of Search: 370/85.1, 370/85.6, 370/85.2, 340/825.5, 340/825.51, 364/131, 364/133, 364/136
• US Class Current: 370/462
• CPC Class Codes: H04Q 11/0457 Connection protocols
• CPC Class Codes: H04Q 2213/05 Software aspects
• CPC Class Codes: H04Q 2213/107 Control equipment for part of the connection

Abstract

An architecture for a switching node of a communication network includes a dedicated hardware Layer 1 processing portion and a Layer 2 and 3 processing portion based on multiple programmed general purpose processors. An array of such processors are used with an arbitration scheme for selecting which of the processors is to be used for any given Layer 2 or Layer 3 process. The architecture allows the node'"'"'s capacity to be expanded by simply adding more processors to handle increased traffic.

Claims

1. A method of arbitrating among a plurality of processors sharing a common bus to determine which one of said processors obtains access to said bus, comprising the steps of:

assigning an arbitrary unique processor number N to each of said processors;

assigning a constant β

to each of said processors, said constant being indicative of the relative computing power of each of said processors;

determining how many previous unsuccessful attempts F each of said processors has made to access said common bus, where F is an integer;

computing a priority number PN for each of said processors as follows

space="preserve" listing-type="equation">PN=CON{β

F, N};

and

granting access to said common bus to said processor having the largest value of PN.

2. The method of claim 1, wherein each of said processors carries out the steps of determining and computing for its own priority number.

3. The method of claim 1 wherein said granting step includes the steps of:

each of said processors floating it'"'"'s own priority number on said common bus, said common bus being an open collector bus;

carrying out a bit by bit comparison of each processor'"'"'s own priority number with each bit of the bus; and

accesing said bus if said processor'"'"'s priority is higher than the priority number appearing on the bus.

4. The method of claim 1, wherein β

is different of at least two of said processors.

5. A method of arbitrating between a plurality of queues to determine which of said queues is granted acess to a common bus, comprising the steps of:

providing a queue controller for each of said queues;

assigning an arbitrary unique queue number N to each of said controllers;

determining how much information is backed up in said queue and assigning a number L representing that backup;

determining how many previous unsuccessful attempts F each said controller has made to access said common bus, where F is an integer;

computing a priority number PN for each of said controllers are follows;

space="preserve" listing-type="equation">PN=CON{(α

L+β

F), (N)}

where α and

β

are constants; and

granting access to said common bus to said controller having the largest value of PN.

6. The method of claim 5, wherein each of said controllers carries out the steps of determining and computing for its own priority number.

7. The method of claim 5, wherein said granting step includes the steps of:

each of said controllers floating it'"'"'s own priority number on said common bus, common bus being an open collector bus;

carrying out a bit by bit comparison of each controller'"'"'s own priority number with each bit of the bus; and

accessing said bus if said controller'"'"'s priority is higher than the priority number appearing on the bus.

8. The method of claim 5, wherein each of said queues is associated with a subscriber line.

9. The method of claim 8, wherein a first of said queues and it'"'"'s associated subscriber line is given a higher service priority than a second of said queues and subscriber lines by setting one of α

and β

higher for said first queue than said second queue.

10. The method of claim 5, wherein a first of said queues is given a higher service priority than a second of said queues by setting one of α

and β

higher for said first queue than said second queue.