Reservation-based media access controller and reservation-based optical network

• US 7,009,991 B2
• Filed: 05/31/2002
• Issued: 03/07/2006
• Est. Priority Date: 03/28/2002
• Status: Expired due to Fees

• Current Assignee: Matisse Networks
• Original Assignee: Matisse Networks
• Inventors: Shachar, Shlomo, Moshe, Oren
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US10/157,871
• Publication Number:
  US 20030185229A1
• Time in Patent Office: 1,376 Days
• Field of Search: 370/252, 370/337, 370/344, 370345-348, 370/430, 370/436, 370/437, 370/442, 370/443, 370/458, 370/478, 370/480, 370/332, 370/498, 370/238, 370/450, 370/223, 398/123, 398/7, 398/8, 398/47, 398/75, 398/99, 359/237, 359/325, 359/119, 455/12.1, 375/356, 709/200, 709/238, 709/223, 385/16
• US Class Current: 370/436
• CPC Class Codes: H04L 12/43 with synchronous transmission, e.g. time division multiplex [TDM], slotted rings
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 2011/0033 using time division switching
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects
• CPC Class Codes: H04Q 2011/0086 Network resource allocation, dimensioning or optimisation
• CPC Class Codes: H04Q 2011/0092 Ring

Abstract

A method and apparatus for reserving bandwidth in a network includes a series of elements. A demand matrix is calculated, for bandwidth requirements based upon communication needs among a plurality of nodes on the network. An integer number of time slots is provided, aligned around the network. Bandwidth is reserved for node-to-node communication based upon the demand matrix. The reserving of bandwidth reserves bandwidth between two nodes based upon time-slot alignment. Transmission is scheduled between the two nodes by reservation of wavelengths and time slots.

Claims

1. A method of reserving bandwidth in a network, said method comprising the steps of:

providing a network having a plurality of nodes thereupon;

calculating a demand matrix for bandwidth requirements based upon communication needs among the plurality of nodes;

providing any integer number of time slots aligned around the network, in which alignment is provided through synchronization;

reserving bandwidth for node-to-node communication based upon the demand matrix, said reserving of bandwidth including reserving bandwidth between two nodes based on time-slot alignment; and

scheduling transmission between the two nodes by reservation of wavelengths and time slots through a reservation map based upon at least the demand matrix.

2. A method of reserving bandwidth in a network as recited in claim 1, wherein said step of providing an optical fiber network having dual optical fiber rings.

3. A method as recited in claim 2, wherein said method includes a step of classifying data into critical and non-critical data, wherein critical data is transmitted on a first fiber ring and a second fiber ring of said dual fiber rings, and wherein non-critical data is transmitted on the first fiber ring.

4. A method as recited in claim 3, wherein said method includes the steps of:

determining an occurrence of a fault in said first or second fiber ring;

re-calculating the demand matrix based upon the occurrence of the fault; and

transmitting non-critical packets on an appropriate one of said first and second fiber rings so as to reach a destination node.

5. A method as recited in claim 1, said method including a step of transmitting a multicast packet from a source node to a plurality of destination nodes, said step of transmitting comprises transmitting the packet to a first node among the plurality of destination nodes, then transmitting the packet from the source node to a second node of said plurality of nodes;

upon receipt of the packet, each receiving node then transmits the packet to two additional destination nodes, until all destination nodes have received the packet.

6. A method as recited in claim 1, said method including a step of transmitting a multicast packet from a source node to a plurality of destination nodes, said step of transmitting comprises transmitting the packet from the source node to a first two destination nodes, and wherein each of said first two destination nodes transmits the packet to two other destination nodes, whereby each destination node forwards the packet to two additional destination nodes until all appropriate nodes have received the packet.

7. A method as recited in claim 1, said method including a step of transmitting a multicast packet from a source node to a first destination node, and wherein said first destination node forwards the packet to a second destination node, and wherein the second destination node forwards the packet to a third destination node, with this process continuing until all destination nodes have received the multicast packet.

8. A method as recited in claim 1, wherein said step of reserving bandwidth comprises constructing a reservation map based upon at least the demand matrix and collision groups.

11. A method as recited in claim 3, wherein said non-critical data is transmitted only on the first fiber ring, and not on the second fiber ring, unless a fault is detected.

12. A method as recited in claim 1, wherein said method reserves bandwidth in an optical fiber ring network.

13. A method as recited in claim 1, wherein said method reserves bandwidth in a local area network.

9. A method of reserving bandwidth in a network, said method comprising the steps of:

providing a network having a plurality of nodes thereupon;

calculating a demand matrix for bandwidth requirements based upon communication needs among the plurality of nodes;

providing an integer number of time slots aligned around the network;

reserving bandwidth for node-to-node communication based upon the demand matrix, said reserving of bandwidth including reserving bandwidth between two nodes based on time-slot alignment; and

scheduling transmission between the two nodes by reservation of wavelengths and time slots;

wherein said step of reserving bandwidth comprises constructing a reservation map based upon the demand matrix and collision groups; and

wherein said step of constructing a reservation map comprises the steps of;

configuring a bipartite graph based upon the demand matrix and a series of collision groups;

selecting an unallocated time slot from a plurality of time slots in a reservation frame, said time slot having a maximum number of allocation constraints among the unallocated time slots;

modifying the bipartite graph based upon the allocation constraints of said time slot, wherein indications of said allocation constraints are removed from the bipartite graph;

creating a maximum matching set for the adjusted bipartite graph;

decrementing a weight of original graph edges included in the maximum matching set;

creating a reservation map time slot for the selected time slot based upon the maximum matching set; and

updating time slot constraint data according to the maximum matching set.

10. A method as recited in claim 9, said method including the step of:

decrementing a weight of graph edges which are included in the maximum matching set.

14. A method of creating a reservation map for communications, said method comprising the steps of:

creating a demand matrix based upon demand data from a plurality of nodes connected on a network;

configuring a bipartite graph based upon the demand matrix and a series of collision groups;

selecting an unallocated time slot from a plurality of time slots in a reservation frame, said time slot having a maximum number of allocation constraints among the unallocated time slots;

modifying the bipartite graph based upon the allocation constraints of said time slot, wherein indications of said allocation constraints are removed from the bipartite graph;

creating a maximum matching set for the adjusted bipartite graph;

decrementing a weight of original graph edges included in the maximum matching set;

creating a reservation map time slot for the selected time slot based upon the maximum matching set; and

updating time slot constraint data according to the maximum matching set.

15. A method as recited in claim 14, comprising the further steps of:

determining the existence of a fault in the network;

re-creating a demand matrix based upon the determination;

transmitting a selected packet on a first fiber in a first direction, or in a second fiber in a second direction, depending upon a location of a destination node.

16. A method of communicating data between nodes on an optical network, said method comprising the steps of:

generating demand data for each node of a plurality of nodes in an optical network;

creating a demand matrix in at least one node of said plurality of nodes, said demand matrix being based on said demand data,

creating a reservation map for each wavelength and each time slot of a reservation frame comprising a plurality of time slots and a plurality of wavelengths, thereby reserving bandwidth on a per time slot and per wavelength basis;

wherein any integer number of time slots are aligned around the optical network, in which alignment is provided through synchronization.

17. A method as recited in claim 16, further comprising a step of:

determining the existence of a fault in the optical network;

re-creating a demand matrix based upon the determination;

transmitting a selected packet on a first fiber in a first direction, or in a second fiber in a second direction, depending upon a location of a destination node.

18. A media access controller for a network, said media access controller comprising:

a demand matrix unit for generating a demand matrix based upon bandwidth requirements for node-to-node communication; and

a reservation map unit for creating a reservation map based upon the demand matrix, and based upon allocation constraints for time slots and wavelengths in a reservation frame,

wherein the reservation map unit utilizes maximum matching data for communication among a plurality of nodes on the network and the media access controller enables any integer number of time slots to be aligned around the network, in which alignment is provided through synchronization.

22. A media access controller as recited in claim 18, wherein said demand matrix unit and said reservation map unit are configured for operation with an optical ring network.

23. A media access controller as recited in claim 18, wherein said demand matrix unit and said reservation map unit are configured for operation with a local area network.

19. A communications node for an optical fiber network, said communications node comprising:

a fixed wavelength receiver for receiving optical data at a predetermined wavelength;

a tunable wavelength transmitter for transmitting optical data to destination nodes at a plurality of destination wavelengths; and

a media access controller which creates a reservation map for reserving time slots and wavelengths for transmitting data to the plurality of nodes based upon available time slots and wavelengths in the optical fiber ring, said reservation map being based upon a demand matrix wherein the media access controller enables any integer number of time slots to be aligned around the network, in which alignment is provided through synchronization.

20. A communications node as recited in claim 19, wherein said node includes a demand matrix generating unit for generating a demand matrix based upon demand data from the plurality of nodes, and wherein said reservation map is based upon said demand matrix.

21. A communications node as recited in claim 19, wherein said reservation map is created based upon demand matrix data transmitted from another of said plurality of nodes.

24. A media access controller for a network, said media access controller comprising:

a demand matrix unit for generating a demand matrix based upon bandwidth requirements for node-to-node communication;

a reservation map unit for creating a reservation map based upon the demand matrix, and based upon allocation constraints for time slots and wavelengths in a reservation frame,

wherein the reservation map unit utilizes maximum matching data for communication among a plurality of nodes on the network; and

wherein said reservation map unit creates said reservation map by configuring a bipartite graph according to the demand matrix, by selecting a first time-slot from a plurality of unallocated time-slots, said first time slots being selected based upon a maximum number of allocation constraints, updating the bipartite graph based upon the selected first time slot, wherein allocation-constraint vertices, and edges connecting them, are removed, selecting a second time slot from the plurality of unallocated time slots, said second time slots having an updated maximum number of allocation constraints, updating the bipartite graph based upon the second time slot, determining a maximum matching set for the updated graph, and updating the reservation map based upon the maximum matching set.

25. A communications node for an optical fiber network, said communications node comprising:

a fixed wavelength receiver for receiving optical data at a predetermined wavelength;

a tunable wavelength transmitter for transmitting optical data to destination nodes at a plurality of destination wavelengths; and

a media access controller which creates a reservation map for reserving time slots and wavelengths for transmitting data to the plurality of nodes based upon available time slots and wavelengths in the optical fiber ring, said reservation map being based upon demand data from the plurality of nodes;

wherein said media access controller is configured to create said reservation map by configuring a bipartite graph according to the demand matrix, by selecting a first time-slot from a plurality of unallocated time-slots, said first time slots being selected based upon a maximum number of allocation constraints, updating the bipartite graph based upon the selected first time slot, wherein allocation-constraint vertices, and edges connecting them, are removed, selecting a second time slot from the plurality of unallocated time slots, said second time slots having an updated maximum number of allocation constraints, updating the bipartite graph based upon the second time slot, determining a maximum matching set for the updated graph, and updating the reservation map based upon the maximum matching set.

26. A system for reserving bandwidth in a network, said system comprising:

interface means for interfacing with a network having a plurality of nodes thereupon;

calculating means for calculating a demand matrix for bandwidth requirements based upon communication needs among the plurality of nodes;

providing means for providing any integer number of time slots aligned around the network, in which alignment is provided through synchronization;

reserving means for reserving bandwidth for node-to-node communication based upon the demand matrix, said reserving of bandwidth including reserving bandwidth between two nodes based on time-slot alignment;

scheduling means for scheduling transmission between the two nodes by reservation of wavelengths and time slots through a reservation map based upon at least the demand matrix.

27. A system for reserving bandwidth in a network, said system comprising:

interface means for interfacing with a network having a plurality of nodes thereupon;

calculating means for calculating a demand matrix for bandwidth requirements based upon communication needs among the plurality of nodes;

providing means for providing an integer number of time slots aligned around the network;

reserving means for reserving bandwidth for node-to-node communication based upon the demand matrix, said reserving of bandwidth including reserving bandwidth between two nodes based on time-slot alignment;

scheduling means for scheduling transmission between the two nodes by reservation of wavelengths and time slots;

further comprising;

creating means for creating the demand matrix based upon demand data from a plurality of nodes connected on a network;

configuring means for configuring a bipartite graph based upon the demand matrix and a series of collision groups;

selecting means for selecting an unallocated time slot from a plurality of time slots in a reservation frame, said time slot having a maximum number of allocation constraints among the unallocated time slots;

modifying means for modifying the bipartite graph based upon the allocation constraints of said time slot, wherein indications of said allocation constraints are removed from the bipartite graph;

creating means for creating a maximum matching set for the adjusted bipartite graph;

decrementing means for decrementing a weight of original graph edges included in the maximum matching set;

creating means for creating a reservation map time slot for the selected time slot based upon the maximum matching set; and

updating means for updating time slot constraint data according to the maximum matching set.

28. A system as recited in claim 27, said system further comprising:

determining means for determining an occurrence of a fault in said first or second fiber ring;

re-calculating means for re-calculating the demand matrix based upon the occurrence of the fault; and

transmitting means for transmitting non-critical packets on an appropriate one of said first and second fiber rings so as to reach a destination node.

29. A system for creating a reservation map for communications, said system comprising:

creating means for creating a demand matrix based upon demand data from a plurality of nodes connected on a network;

configuring means for configuring a bipartite graph based upon the demand matrix and a series of collision groups;

selecting means for selecting an unallocated time slot from a plurality of time slots in a reservation frame, said time slot having a maximum number of allocation constraints among the unallocated time slots;

modifying means for modifying the bipartite graph based upon the allocation constraints of said time slot, wherein indications of said allocation constraints are removed from the bipartite graph;

creating means for creating a maximum matching set for the adjusted bipartite graph;

decrementing means for decrementing a weight of original graph edges included in the maximum matching set;

creating means for creating a reservation map time slot for the selected time slot based upon the maximum matching set; and

updating means for updating time slot constraint data according to the maximum matching set.