Patent US5956342A successfully refreshed from Google Patents.
US5956342A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Priority arbitration for point-to-point and multipoint transmission
Assignee: Ascom Intermediate AG
•
Filing: 1996-07-18
•
Granted: 1999-09-21
•
Expires: 2016-07-18
Abstract
Abstract An Asynchronous Transfer Mode switch and method which facilitate priority arbitration of point-to-point and point-to-multipoint transmission are disclosed. To execute point-to-multipoint operation a bandwidth arbiter maintains a first list of connections and bit vectors indicating designated destination ports. The list maintained by the bandwidth arbiter is then compared to an unassigned output port bit vector to determine matches therebetween at which point-to-multipoint transmission may be made by utilizing instantaneously unused bandwidth within the switch. To execute point-to-point operation each input port maintains a list of connections associated with each output port, and those lists are used in conjunction with output port request information per input port in the bandwidth arbiter to match requests to the unassigned output port bit vector. The bandwidth arbiter may also assign priority to connections in the list.
Inventors
- 👤 Thomas A. Manning
- 👤 Stephen A. Caldara
- 👤 Stephen A. Hauser
- 👤 Matthias L. Colsman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:16
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/18; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17375; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/4608; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L12/64; H04L12/6402; H04L41/00; H04L41/08; H04L41/0896; H04L47/11; H04L47/15; H04L47/16; H04L47/26; H04L47/266; H04L47/29; H04L47/30; H04L47/50; H04L47/52; H04L47/521; H04L47/522; H04L47/525; H04L47/56; H04L47/62; H04L47/621; H04L47/6215; H04L47/622; H04L47/6225; H04L47/625; H04L47/627; H04L47/70; H04L47/72; H04L47/722; H04L47/74; H04L47/743; H04L47/745; H04L47/76; H04L47/762; H04L47/78; H04L47/782; H04L47/80; H04L47/805; H04L47/82; H04L47/822; H04L49/00; H04L49/10; H04L49/101; H04L49/103; H04L49/104; H04L49/105; H04L49/106; H04L49/107; H04L49/108; H04L49/15; H04L49/1515; H04L49/153; H04L49/1553; H04L49/1576; H04L49/20; H04L49/201; H04L49/203; H04L49/205; H04L49/25; H04L49/253; H04L49/254; H04L49/255; H04L49/256; H04L49/30; H04L49/3009; H04L49/3081; H04L49/309; H04L49/45; H04L49/455; H04L49/50; H04L49/501; H04L49/503; H04L49/505; H04L49/506; H04L49/55; H04L49/552; H04L49/90; H04L49/901; H04L49/9047; H04L49/9063; H04L49/9078; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/324; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04W; H04W28/00; H04W28/02; H04W28/10; H04W28/14; H04J; H04J3/00; H04J3/02; H04J3/06; H04J3/0635; H04J3/0682; H04J3/0685; H04L2012/5614; H04L2012/5616; H04L2012/5625; H04L2012/5627; H04L2012/5628; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5634; H04L2012/5635; H04L2012/5638; H04L2012/564; H04L2012/5642; H04L2012/5643; H04L2012/5646; H04L2012/5647; H04L2012/5648; H04L2012/5649; H04L2012/565; H04L2012/5651; H04L2012/5652; H04L2012/5672; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682; H04L2012/5683; H04L2012/5684; H04L2012/5685; H04L41/0897; H04L41/40; H04L49/508; H04L49/555; H04L7/00; H04L7/04; H04L7/041; H04L7/046; Y; Y10; Y10S; Y10S370/00; Y10S370/901; Y10S370/902; Y10S370/903; Y10S370/905
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
259 words
A network switch for facilitating point-to-point and point-to-multipoint transmission of units of data associated with connections, comprising: a plurality of output ports; a plurality of input ports each operative to receive units of data from outside said switch and transmit the received units of data to at least one of the output ports; an allocation map operative to store a representation of bandwidth that is allocated within the switch in a plurality of future data unit time intervals; a point-to-multipoint request map operative to store a representation of units of data enqueued for point-to-multipoint transmission in a present data unit time interval; a point-to-point request map operative to store a representation of units of data enqueued for point-to-point transmission in a present data unit time interval; and a matching operator which functions to identify unallocated bandwidth and allocated-unused bandwidth that may be employed to transmit ones of the units of data represented in said point-to-multipoint request map and said point-to-point request map during a data unit time interval immediately following the present data unit time interval, and selects ones of the units of data represented in said point-to-multipoint request map and said point-to-point request map for transmission in the data unit time interval immediately following the present data unit time interval so that collisions are avoided, whereby unallocated bandwidth and allocated-unused bandwidth are utilized for transmission of units of data enqueued for point-to-point and point-to-multipoint transmission when matching unallocated bandwidth and allocated-unused bandwidth becomes available in the data unit time interval immediately following the present data unit time interval.
Claim 2
Dependent Claim
259 words
A network switch for facilitating point-to-point and point-to-multipoint transmission of units of data associated with connections, comprising: a plurality of output ports; a plurality of input ports each operative to receive units of data from outside said switch and transmit the received units of data to at least one of the output ports; an allocation map operative to store a representation of bandwidth that is allocated within the switch in a plurality of future data unit time intervals; a point-to-multipoint request map operative to store a representation of units of data enqueued for point-to-multipoint transmission in a present data unit time interval; a point-to-point request map operative to store a representation of units of data enqueued for point-to-point transmission in a present data unit time interval; and a matching operator which functions to identify unallocated bandwidth and allocated-unused bandwidth that may be employed to transmit ones of the units of data represented in said point-to-multipoint request map and said point-to-point request map during a data unit time interval immediately following the present data unit time interval, and selects ones of the units of data represented in said point-to-multipoint request map and said point-to-point request map for transmission in the data unit time interval immediately following the present data unit time interval so that collisions are avoided, whereby unallocated bandwidth and allocated-unused bandwidth are utilized for transmission of units of data enqueued for point-to-point and point-to-multipoint transmission when matching unallocated bandwidth and allocated-unused bandwidth becomes available in the data unit time interval immediately following the present data unit time interval.
Claim 3
Dependent Claim
35 words
The network switch of claim 1 wherein said point-to-multipoint request map includes a connection field operative to store a representation of the connection associated with each of the units of data enqueued for point-to-multipoint transmission.
Claim 4
Dependent Claim
37 words
The network switch of claim 2 wherein said point-to-multipoint request map further includes a bit vector field operative to store a representation of the output ports to which each point-to-multipoint unit of data is to be transmitted.
Claim 5
Dependent Claim
48 words
The network switch of claim 3 wherein said allocation map includes a switch allocation table operative to store an index identifier and an allocation table operative to store a bitmask which represents unallocated bandwidth and allocated-unused bandwidth within the switch, said allocation table indexed by said index identifier.
Claim 6
Dependent Claim
47 words
The network switch of claim 1 wherein said matching operator functions to match at least one of unallocated bandwidth and allocated-unused bandwidth to each unit of data enqueued for point-to-multipoint transmission via unallocated bandwidth and allocated-unused bandwidth sequentially starting from the first enqueued point-to-multipoint unit of data.
Claim 7
Dependent Claim
45 words
The network switch of claim 5 wherein the enqueued point-to-multipoint units of data are prioritized into at least two separate groups and said matching operator functions to provide opportunity for selection to higher priority groups prior to providing opportunity for selection to lower priority groups.
Claim 8
Dependent Claim
44 words
The network switch of claim 3 wherein said matching operator generates an unassigned output port bit vector which is compared with said bit vector field to provide opportunities to select the enqueued point-to-multipoint units of data for transmission via unallocated bandwidth and allocated-unused bandwidth.
Claim 9
Dependent Claim
52 words
The network switch of claim 7 wherein said request map includes a first pointer for indicating the order in which enqueued point-to-multipoint units of data are provided with opportunities for selection by said matching operator, said pointer being incremented to provide a round-robin type ordering of unit of data matching! selection opportunities.
Claim 10
Dependent Claim
56 words
The network switch of claim 1 wherein each input port includes a To Switch Port Processor ("TSPP") having a connection list of point-to-point connections associated with each output port, said lists of point-to-point connections storing representations of connections having a unit of data enqueued for the respective output port with which the respective list is associated.
Claim 11
Dependent Claim
54 words
The network switch of claim 9 wherein said point-to-point request map includes a point-to-point request bit vector for each said TSPP, said point-to-point request bit vector indicating each output port to which a point-to-point unit of data is to be transmitted from the respective TSPP with which the point-to-point request bit vector is associated.
Claim 12
Dependent Claim
36 words
The network switch of claim 10 including a first pointer operative to select a point-to-point request bit vector for being provided with opportunities for selection by said matching operator in a round robin manner of selection.
Claim 13
Dependent Claim
42 words
The network switch of claim 11 including a second pointer operative to select an output port bit within said point-to-point request bit vector for being provided with the opportunity for selection by said matching operator in a round robin manner of selection.
Claim 14
Independent Claim
118 words
A method for point-to-point and point-to-multipoint transmission of units of data in a network switch comprising the steps of: in a first storing step, storing a representation of the unit of data in a first list; in a second storing step, storing a representation of dynamic bandwidth that includes both unallocated bandwidth and allocated-unused bandwidth in a second list; comparing the first list with the second list to determine if at least one representation in said first list matches at least one representation in said second list; and if a match is determined to exist in said comparing step, transmitting at least one unit of data for which the match is determined to exist via the dynamic bandwidth.
Claim 15
Independent Claim
118 words
A method for point-to-point and point-to-multipoint transmission of units of data in a network switch comprising the steps of: in a first storing step, storing a representation of the unit of data in a first list; in a second storing step, storing a representation of dynamic bandwidth that includes both unallocated bandwidth and allocated-unused bandwidth in a second list; comparing the first list with the second list to determine if at least one representation in said first list matches at least one representation in said second list; and if a match is determined to exist in said comparing step, transmitting at least one unit of data for which the match is determined to exist via the dynamic bandwidth.
Claim 16
Dependent Claim
41 words
The method of claim 13 wherein said first storing step includes the further step of storing a request map including a connection field operative to store a representation of the connection associated with each unit of data enqueued for point-to-multipoint transmission.
Claim 17
Dependent Claim
35 words
The method of claim 14 wherein said first storing step includes the further step of storing a request bit vector representation of each output port to which the unit of data is to be transmitted.
Claim 18
Dependent Claim
25 words
The method of claim 15 wherein said second storing step includes the further step of storing a bitmask which represents dynamic bandwidth within the switch.
Claim 19
Dependent Claim
24 words
The method of claim 16 wherein said comparing step includes the further step of comparing the dynamic bandwidth bitmask with the request bit vector.
Claim 20
Dependent Claim
60 words
The method of claim 17 wherein a plurality of request bit vectors are stored and said comparing step includes the further step of prioritizing the request bit vectors into at least two separate groups arranged from high priority to low priority, said comparing step being performed upon higher priority request bit vectors prior to said lower priority request bit vectors.
Claim 21
Dependent Claim
52 words
The method of claim 17 wherein the request bitmask field includes a pointer for indicating which the order in which enqueued units of data are first matched to dynamic bandwidth, said comparing step including the further step of incrementing the pointer to provide a round-robin type ordering of unit of data matching.
Claim 22
Dependent Claim
43 words
The method of claim 13 wherein said first storing step includes storing a point-to-point request bit vector for each input port in the switch, the request bit vectors containing a indicator of each output port requested by each input port in the switch.
Claim 23
Dependent Claim
40 words
The method of claim 20 wherein said first storing step includes the further step of storing a plurality of lists of point-to-point connections having a unit of data enqueued for respective output ports with which the respective list is associated.
Claim 24
Dependent Claim
178 words
An asynchronous transfer mode ("ATM") switch for arbitrating transmission of point-to-point cells and point-to-multipoint cells in a present data unit time interval, comprising: a plurality of input ports operative to receive cells comprising point-to-point cells and point-to-multipoint cells; a plurality of output ports operative to transmit said received cells from said switch; a switch fabric operative to selectively forward said cells from said plurality of input ports to selected ones of said plurality of output ports; and an arbitration operator operative to match ones of the point-to-point cells and ones of the point-to-multipoint cells to dynamic bandwidth that comprises unallocated bandwidth and allocated-unused bandwidth in a data unit time interval immediately following the present data unit time interval, said arbitration operator also operative to determine which cells received in said plurality of input ports are forwarded to said plurality of output ports through said switch fabric such that point-to-point and point-to-multipoint cells which are matched to dynamic bandwidth by said arbitration operator are forwarded to specified ones of said plurality of output ports so as to avoid collisions.
Claim 25
Dependent Claim
178 words
An asynchronous transfer mode ("ATM") switch for arbitrating transmission of point-to-point cells and point-to-multipoint cells in a present data unit time interval, comprising: a plurality of input ports operative to receive cells comprising point-to-point cells and point-to-multipoint cells; a plurality of output ports operative to transmit said received cells from said switch; a switch fabric operative to selectively forward said cells from said plurality of input ports to selected ones of said plurality of output ports; and an arbitration operator operative to match ones of the point-to-point cells and ones of the point-to-multipoint cells to dynamic bandwidth that comprises unallocated bandwidth and allocated-unused bandwidth in a data unit time interval immediately following the present data unit time interval, said arbitration operator also operative to determine which cells received in said plurality of input ports are forwarded to said plurality of output ports through said switch fabric such that point-to-point and point-to-multipoint cells which are matched to dynamic bandwidth by said arbitration operator are forwarded to specified ones of said plurality of output ports so as to avoid collisions.
Claim 26
Dependent Claim
51 words
The ATM switch of claim 22 wherein point-to-multipoint cells matched to the dynamic bandwidth are directed to specified ones of said plurality of output ports by said arbitration operator before point-to-point cells which match dynamic bandwidth are directed to specified ones of said plurality of output ports by said arbitration operator.
Claim 27
Dependent Claim
27 words
The ATM switch of claim 22 wherein said arbitration operator prioritizes the point-to-point cells into at least first and second groups of higher and lower priority, respectively.
Claim 28
Dependent Claim
27 words
The ATM switch of claim 24 wherein said arbitration operator prioritizes the point-to-multipoint cells into at least first and second groups of higher and lower priority, respectively.
Claim 29
Dependent Claim
22 words
The ATM switch of claim 25 wherein said high priority groups are matched to dynamic bandwidth prior to said low priority groups.
Claim 30
Dependent Claim
24 words
The ATM switch of claim 26 wherein said high priority point-to-multipoint cells are matched to dynamic bandwidth prior to said high priority point-to-point cells.
Claim 31
Dependent Claim
24 words
The ATM switch of claim 27 wherein said low priority point-to-multipoint cells are matched to dynamic bandwidth prior to said low priority point-to-point cells.
Claim 32
Dependent Claim
43 words
The ATM switch of claim 22 wherein said arbitration operator maintains a record of each point-to-point cells at least until such cell enters said switch fabric, said record including an indication of the output port to which the cell is to be transmitted.
Claim 33
Dependent Claim
43 words
The ATM switch of claim 29 wherein said arbitration operator maintains a record of each point-to-multipoint cell at least until such cell enters said switch fabric, said record including an indication of the output ports to which the cell is to be transmitted.
Claim 34
Dependent Claim
47 words
The ATM switch of claim 30 wherein when a point-to-point cell is received in an input port, a corresponding request message is sent to said arbitration operator indicating that the cell is enqueued and identifying the output port to which the point-to-point cell is to be transmitted.
Claim 35
Dependent Claim
27 words
The ATM switch of claim 31 wherein, when the point-to-point cell is dequeued, a drop request message is sent to said arbitration operator from said input port.
Claim 36
Dependent Claim
285 words
A network switch having a plurality of input ports for receiving data units associated with connections at the respective input ports, a plurality of output ports for transmitting data units associated with said connections to communication links coupled to the respective output ports, said network switch comprising: bandwidth allocation data structures operative to store a representation of output ports which are available for receipt of data units from input ports competing for such output ports during an imminent data unit time interval; a first set of request data structures operative to store an indication of data units enqueued for transmission from one of said plurality of input ports to at least two of said plurality of output ports; a second set of request data structures operative to store an indication of data units enqueued for transmission from at least one of said plurality of input ports to a respective selected one of said plurality of output ports for each of said input ports having a data unit enqueued for transmission; matching control logic operative to match indications of data units enqueued for transmission in said first and second request sets of data structures with available output ports available for receipt of said data units competing for such output ports during said imminent data unit time interval; and arbitration logic operative to forward selected ones of said data units from selected ones of said input ports to selected ones of said output ports upon matching of said indications of selected ones of said data units enqueued for transmission in said first and second request sets of data structures with said output ports available for receipt of data units as reflected in said bandwidth allocation data structures.
Claim 37
Dependent Claim
285 words
A network switch having a plurality of input ports for receiving data units associated with connections at the respective input ports, a plurality of output ports for transmitting data units associated with said connections to communication links coupled to the respective output ports, said network switch comprising: bandwidth allocation data structures operative to store a representation of output ports which are available for receipt of data units from input ports competing for such output ports during an imminent data unit time interval; a first set of request data structures operative to store an indication of data units enqueued for transmission from one of said plurality of input ports to at least two of said plurality of output ports; a second set of request data structures operative to store an indication of data units enqueued for transmission from at least one of said plurality of input ports to a respective selected one of said plurality of output ports for each of said input ports having a data unit enqueued for transmission; matching control logic operative to match indications of data units enqueued for transmission in said first and second request sets of data structures with available output ports available for receipt of said data units competing for such output ports during said imminent data unit time interval; and arbitration logic operative to forward selected ones of said data units from selected ones of said input ports to selected ones of said output ports upon matching of said indications of selected ones of said data units enqueued for transmission in said first and second request sets of data structures with said output ports available for receipt of data units as reflected in said bandwidth allocation data structures.
Claim 38
Dependent Claim
78 words
The network switch of claim 33 wherein the matching control logic is operative to match indications of data units enqueued for transmission in said first set of data structures with available output ports available for receipt of said data units competing for such output ports during said specified time intervals prior to matching indications of data units enqueued for transmission in said second set of data structures with available output ports available for receipt of said data units.
Claim 39
Dependent Claim
38 words
The network switch of claim 33 wherein said arbitration logic is operative to prioritize data units represented in the second set of request data structures into at least first and second groups of higher and lower priority, respectively.
Claim 40
Dependent Claim
38 words
The network switch of claim 35 wherein said arbitration logic is operative to prioritize data units represented in the first set of request data structures into at least first and second groups of higher and lower priority, respectively.
Claim 41
Dependent Claim
44 words
The network switch of claim 36 wherein the matching control logic is operative to match data units represented in each of said high priority groups with available output ports prior to matching data units represented in said low priority groups with available output ports.
Claim 42
Dependent Claim
56 words
The network switch of claim 37 wherein the matching control logic is operative to match data units represented in the first group of the first set of request data structures to available output ports prior to matching data units represented in the first group of the second set of request data structures to available output ports.
Claim 43
Dependent Claim
56 words
The network switch of claim 38 wherein the matching control logic is operative to match data units represented in the second group of the first set of request data structures to available output ports prior to matching data units represented in the second group of the second set of request data structures to available output ports.
Claim 44
Dependent Claim
36 words
The network switch of claim 33 wherein said arbitration logic maintains an indication of each output port from which each data unit represented in the second set of request data structures is enqueued to be transmitted.
Claim 45
Dependent Claim
36 words
The network switch of claim 40 wherein said arbitration logic maintains an indication of each output port from which each data unit represented in the first set of request data structures is enqueued to be transmitted.
Claim 46
Dependent Claim
60 words
The network switch of claim 41 wherein a request message corresponding to each data unit represented in the second set of request data structures is communicated from the associated input port to the arbitration logic, the request message indicating that such data unit is enqueued and indicating the output port to which such data unit is enqueued to be transmitted.
Claim 47
Dependent Claim
28 words
The network switch of claim 42 wherein, when such data unit is dequeued, a drop request message is communicated to the arbitration logic from the associated input port.
References Cited (Backward Citations)
US3804991A
Cited
US3974343A
Cited
US4069399A
Cited
US4603382A
Cited
US4849968A
Cited
US4727537A
Cited
US4737953A
Cited
US4715030A
Cited
US4821034A
Cited
US4993018A
Cited
US4920531A
Cited
US4878216A
Cited
US4797881A
Cited
US4837761A
Cited
US5084871A
Cited
US5335325A
Cited
US5282201A
Cited
US4893307A
Cited
US5021949A
Cited
US4870641A
Cited
US4872159A
Cited
US4958341A
Cited
US4872160A
Cited
US4893302A
Cited
US4894824A
Cited
US4899333A
Cited
US4979100A
Cited
US5377327A
Cited
US5146560A
Cited
US4956839A
Cited
US5198808A
Cited
US4922503A
Cited
US5060228A
Cited
US5157657A
Cited
US5090011A
Cited
US5083269A
Cited
US4897841A
Cited
US5199027A
Cited
US4933938A
Cited
US4947390A
Cited
US5132966A
Cited
US4953157A
Cited
US5119372A
Cited
US5179558A
Cited
US5093912A
Cited
US5422879A
Cited
US5130982A
Cited
US5067123A
Cited
US5119369A
Cited
US5070498A
Cited
US5090024A
Cited
US5193151A
Cited
US5197067A
Cited
US5084867A
Cited
US5191652A
Cited
US5163046A
Cited
US5130975A
Cited
US5185743A
Cited
US5272697A
Cited
US5379418A
Cited
US5544170A
Cited
US5553068A
Cited
US5309431A
Cited
US5258979A
Cited
US5151897A
Cited
US5239539A
Cited
US5146474A
Cited
US5029164A
Cited
US5303232A
Cited
US5253248A
Cited
US5341376A
Cited
US5115429A
Cited
US5301190A
Cited
US5335222A
Cited
US5333131A
Cited
US5253247A
Cited
US5274641A
Cited
US5150358A
Cited
US5128932A
Cited
US5420988A
Cited
US5267232A
Cited
US5283788A
Cited
US5163045A
Cited
US5414703A
Cited
US5394396A
Cited
US5271010A
Cited
US5255266A
Cited
US5497369A
Cited
US5268897A
Cited
US5301193A
Cited
US5280470A
Cited
US5285446A
Cited
US5375117A
Cited
US5333134A
Cited
US5341373A
Cited
US5287349A
Cited
US5590132A
Cited
US5479402A
Cited
US5339310A
Cited
US5487063A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-20 | 2003-03-22 | 2003-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-20 | 2007-03-22 | 2007-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-20 | 2011-03-22 | 2011-09-21 | $7700.00 | Window Closed / Lapsed |