Advertisement
- Home
- Programming
- Languages
- C
- Computing Ratios between elements in an array
Advertisement
- 1. Infinity08 225,571
- 2. evilrix 121,501
- 3. jkr 67,934
- 4. ozo 48,235
- 5. josgood 26,525
- 6. itsmeand... 22,659
- 7. jaime_ol... 18,880
- 8. Kdo 18,780
- 9. sunnycoder 17,740
- 10. fridom 15,943
- 11. Gurudenis 7,180
- 12. hielo 6,200
- 13. duncan_roe 5,600
- 14. ravenpl 5,590
- 15. PaulCaswell 5,372
- 1. sunnycoder 804,283
- 2. Infinity08 758,430
- 3. Kdo 745,278
- 4. jkr 678,696
- 5. ozo 390,543
- 6. grg99 296,356
- 7. PaulCaswell 295,931
- 8. brettmjo... 182,528
- 9. jaime_ol... 174,552
- 10. ankuratvb 157,866
- 11. evilrix 151,366
- 12. itsmeand... 151,125
- 13. fridom 146,547
- 14. imladris 137,967
- 15. cwwkie 129,383
| 03.26.2008 at 12:37PM PDT, ID: 23271825 |
|
[x]
Attachment Details
|
||
|
[x]
The Solution Rating System
|
||
|
With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.
Your Input Matters If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support. Thank you! |
||
Computing Ratios between elements in an array
Tags:
c++
Hi experts,
I need your help to get going on this.
Problem: I have a tree with a root node connected to 3 (or more) children. Each edge between a parent and child has a certain cost (integer) associated with it. If a child node needs to send a packet to the root node, it has the following three ways to do so:
1. Select a path with minimum (or maximum) cost value and stick to it.
2. alternate between all available paths, i.e., send 1 packet on one path, 2nd on the 2nd path, etc. etc.
3. compute ratio of minimum/maximum cost paths and send n number of packets on each path depending on this ratio. e.g., if we have ratio of 1:2, then send 1 packet on 1 path, and 2 packets on the 2nd path.
regarding 3rd option, If I have all the cost paths stored in an array, how do i compare the ratio's b/w each element in this array to determine how many packets to send on each path? sorry if this is too basic.. I just need help to get started.
thanks in advance.
Start your free trial to view this solution
I need your help to get going on this.
Problem: I have a tree with a root node connected to 3 (or more) children. Each edge between a parent and child has a certain cost (integer) associated with it. If a child node needs to send a packet to the root node, it has the following three ways to do so:
1. Select a path with minimum (or maximum) cost value and stick to it.
2. alternate between all available paths, i.e., send 1 packet on one path, 2nd on the 2nd path, etc. etc.
3. compute ratio of minimum/maximum cost paths and send n number of packets on each path depending on this ratio. e.g., if we have ratio of 1:2, then send 1 packet on 1 path, and 2 packets on the 2nd path.
regarding 3rd option, If I have all the cost paths stored in an array, how do i compare the ratio's b/w each element in this array to determine how many packets to send on each path? sorry if this is too basic.. I just need help to get started.
thanks in advance.
Question Stats
Zone:
Programming
Question Asked By:
omerkh
Solution Provided By:
Infinity08
Participating Experts:
3
Solution Grade:
A
Views:
0
Translate:
Loading Advertisement...
Loading Advertisement...
| Microsoft |
- Internet Protocols
- Applications
- Development
- OS
- Hardware
- Windows Security
| Apple |
- Operating Systems
- Hardware
- Programming
- Networking
- Software
| Internet |
- Search Engines
- File Sharing
- WebTrends / Stats
- Spy / Ad Blockers
- Web Browsers
- New Net Users
- Web Development
- Chat / IM
- Anti Spam
- Web Servers
- Anti-Virus
- Email Clients
| Gamers |
- Tips
- Online / MMORPG
- Puzzle
- Emulators
- Action / Adventure
- Role Playing
- Consoles
- Game Programming
- Strategy
- Sports
- Misc
- Computer Games
| Digital Living |
- Hardware
- New Net Users
- New Users
- Software
- Digital Music
- Gaming World
- Home Security
- Apple
- Networking Hardware
| Virus & Spyware |
- Vulnerabilities
- IDS
- Encryption
- Anti-Virus
- Operating Systems Security
- Software Firewalls
- WebApplications
- Cell Phones
- Operating Systems
- Internet
- Hardware Firewalls
| Hardware |
- Handhelds / PDAs
- Displays / Monitors
- Components
- Networking Hardware
- Peripherals
- Laptops/Notebooks
- Storage
- Servers
- Desktops
- New Users
- Misc
- Apple
| Software |
- System Utilities
- Industry Specific
- Network Management
- Photos / Graphics
- Page Layout
- VMWare
- Misc
- Web Development
- OS
- CYGWIN
- Voice Recognition
- Message Queue
- Quality Assurance
- Security
- Firewalls
- MultiMedia Applications
- Development
- Database
- Office / Productivity
- Business Management
- OS/2 Apps
- Server Software
- Internet / Email
| ITPro |
- OS
- Storage
- Encryption
- Operating Systems Security
- Apple Hardware
- Laptops & Notebooks
- Servers
- Networking Hardware
- Peripherals
- Devices
- Displays / Monitors
- WebTrends / Stats
- Search Engines
- Firewalls
- WebApplications
- IDS
- Vulnerabilities
- Email Clients
- File Sharing
- Spy / Ad Blockers
- Web Browsers
- Web Servers
- Networking
- Anti-Virus
- Chat / IM
- Anti Spam
| Developer |
- Web Servers
- Web Browsers
- Game Programming
- Dev Tools
- Industry Specific
- Office / Productivity
- Database
- CYGWIN
- Web Development
- Search Engines
- File Sharing
- WebTrends / Stats
- Programming
- Content Management
- Application Servers
- Protocols
| Storage |
- Removable Backup Media
- Storage Technology
- Servers
- Grid
- Remote Access
- Backup / Restore
- Misc
- Hard Drives
| OS |
- Miscellaneous
- Security
- Development
- Linux
- VMWare
- MainFrame OS
- Unix
- Apple
- OS / 2
- AS / 400
- BeOS
- Microsoft
- VMS / OpenVMS
| Database |
- Oracle
- Miscellaneous
- MySQL
- Software
- Sybase
- Contact Management
- PostgreSQL
- Data Manipulation
- Clarion
- InterSystems Cache
- Siebel
- MUMPS
- OLAP
- SQLBase
- SAS
- GIS & GPS
- 4GL
- Berkeley DB
- DB2
- Informix
- Interbase / Firebird
- FoxPro
- Reporting
- LDAP
- Filemaker Pro
- MS SQL Server
- dBase
- MS Access
| Security |
- Misc
- Web Browsers
- Software Firewalls
- Operating Systems Security
- File Sharing
- Spy / Ad Blockers
- Vulnerabilities
- WebApplications
- IDS
- Anti-Virus
- Encryption
- Anti Spam
- Email Clients
- VPN
- Chat / IM
| Programming |
- Editors IDEs
- Installation
- Handhelds / PDAs
- Multimedia Programming
- System / Kernel
- Algorithms
- Game
- Signal Processing
- Project Management
- Open Source
- Database
- Misc
- Languages
- Processor Platforms
- Theory
| Web Development |
- Scripting
- Blogs
- Web Servers
- Software
- Search Engines
- Web Graphics
- Images
- Internet Marketing
- Images and Photos
- Components
- Document Imaging
- Web Languages/Standards
- Illustration
- WebApplications
- Fonts
- WebTrends / Stats
- Authoring
- Digital Camera Software
- Miscellaneous
| Networking |
- Protocols
- Apple Networking
- Network Management
- Message Queue
- Application Servers
- Content Management
- File Servers
- Email Servers
- Misc
- Java Editors & IDEs
- Wireless
- Networking Hardware
- Backup / Restore
- System Utilities
- ISPs & Hosting
- Web Servers
- Storage Technology
- Removable Backup Media
- Servers
- Broadband
- Grid
- OS / 2
- Novell Netware
- Unix Networking
- Windows Networking
- Security
- Telecommunications
- Operating Systems
- Linux Networking
| Other |
- Community Advisor
- Lounge
- Community Support
- New Net Users
- Philosophy / Religion
- Math / Science
- Miscellaneous
- URLs
- Expert Lounge
- Politics
- Puzzles / Riddles
| Community Support |
- Suggestions
- New to EE
- New Topics
- Community Advisor
- CleanUp
- Announcements
- General
- Feedback
- Input
- EE Bugs
| 03.27.2008 at 02:29AM PDT, ID: 21219665 |
>> If a child node needs to send a packet to the root node
Isn't there only one path between a child and the root ? Otherwise it's not a standard tree ... Can you explain a bit more what the structure is ?
Isn't there only one path between a child and the root ? Otherwise it's not a standard tree ... Can you explain a bit more what the structure is ?
| 03.27.2008 at 03:42AM PDT, ID: 21219972 |
sorry you can omit the word tree from there. please see the jpeg. that shows what i want.
I can have all the cost values stored in an array. I just need to determine that if the child wants to send x amounts of packets to the parent, how do i compare the ratio's b/w each element in this array to determine how many packets to send on each path.
Hope that clarifies.
I can have all the cost values stored in an array. I just need to determine that if the child wants to send x amounts of packets to the parent, how do i compare the ratio's b/w each element in this array to determine how many packets to send on each path.
Hope that clarifies.
| 03.27.2008 at 03:45AM PDT, ID: 21219983 |
sorry: rephrase from above to:
.... that if the child wants to send x amounts of packets to the root ...
.... that if the child wants to send x amounts of packets to the root ...
| 03.27.2008 at 04:06AM PDT, ID: 21220070 |
That's more commonly called a graph, and finding a path in a graph is a graph path finding problem.
What you describe is pretty much a routing algorithm, more specifically multi-path routing or load-balanced routing.
http://ntrg.cs.tcd.ie/undergrad/4ba2
What you describe is pretty much a routing algorithm, more specifically multi-path routing or load-balanced routing.
http://ntrg.cs.tcd.ie/undergrad/4ba2
| 03.27.2008 at 11:47AM PDT, ID: 21224571 |
great.
actually the routing algorithm i have had implemented so far can do the following:
1. Find all available paths from child to root.
2. Choose the most optimum path (depending on any factor, ... say channel cost)
3. send the packets on that chosen path.
But there is a problem here. The 'most optimum path' will suffer from congestion & bottle necks because it would be used more often than the rest. So we do need some kind of load balancing.
load balancing using a round-robin technique is easy to implement. simply alternate between all available paths. but a round-robin is of no use to us because we want to select path by giving more importance to the cost factor.
so this sums it down: what I am having problem in figuring out is how to actually perform load balancing in such a way that greater weightage is given to nodes with minimum cost AND less weightage is given to nodes with maximum cost.
So, as in the diagram, most of the packets being sent would choose the path with cost 1+2=3 .... while less packets would be sent on the remaining paths of cost 2+3=5 ... simply because they are more expensive.
if you know any research paper focussing on such an issue, it would be also very beneficial.
thanks
actually the routing algorithm i have had implemented so far can do the following:
1. Find all available paths from child to root.
2. Choose the most optimum path (depending on any factor, ... say channel cost)
3. send the packets on that chosen path.
But there is a problem here. The 'most optimum path' will suffer from congestion & bottle necks because it would be used more often than the rest. So we do need some kind of load balancing.
load balancing using a round-robin technique is easy to implement. simply alternate between all available paths. but a round-robin is of no use to us because we want to select path by giving more importance to the cost factor.
so this sums it down: what I am having problem in figuring out is how to actually perform load balancing in such a way that greater weightage is given to nodes with minimum cost AND less weightage is given to nodes with maximum cost.
So, as in the diagram, most of the packets being sent would choose the path with cost 1+2=3 .... while less packets would be sent on the remaining paths of cost 2+3=5 ... simply because they are more expensive.
if you know any research paper focussing on such an issue, it would be also very beneficial.
thanks
| 03.27.2008 at 11:57AM PDT, ID: 21224664 |
and to add to that, of the load balancing papers i have seen, they suggest optimization by 'revamping' the graph topology itself. we don't want to do that. the graph topology and connections should remain as is.
| 03.27.2008 at 02:06PM PDT, ID: 21225753 |
It seems relatively easy to me...
Having generated a list of paths, sort them by cost.
Then round-robin though the top (least costly) n items in the list.
How you choose n would become the important issue.
You could decide it using a simple criteria (e.g., choose the best 50% of the paths), or you could use some criteria that takes into account how many (or few) paths are available, or how costly a path will be. For instance, you could shorten the round-robin list to include only paths that cost no more than twice the price of the minimum, best path.
Having generated a list of paths, sort them by cost.
Then round-robin though the top (least costly) n items in the list.
How you choose n would become the important issue.
You could decide it using a simple criteria (e.g., choose the best 50% of the paths), or you could use some criteria that takes into account how many (or few) paths are available, or how costly a path will be. For instance, you could shorten the round-robin list to include only paths that cost no more than twice the price of the minimum, best path.
Assisted Solution
| 03.28.2008 at 07:36AM PDT, ID: 21230785 |
Do you know the time required for a packet to travel an edge? It seems that you want to keep all the channels as busy as possible so that the child does not have to wait longer than necessary to send the next packet from a batch. Also, don't you need to consider load on the root? I.e., can the root process packets as fast as they arrive or can it cause congestion along the routes?
| 03.31.2008 at 06:39AM PDT, ID: 21245210 |
Sorry for the late reply - I've been offline for a few days.
>> so this sums it down: what I am having problem in figuring out is how to actually perform load balancing in such a way that greater weightage is given to nodes with minimum cost AND less weightage is given to nodes with maximum cost.
Unless I'm misunderstanding you, you can just take the inverse of the cost. So, if between a child and the root, there are 3 paths with costs 2, 5 and 20 respectively, then the weights would be 1/2 (= 10/20), 1/5 (= 4/20) and 1/20 respectively, or "normalized" 10/15, 4/15 and 1/15 (in percentages : 66.67%, 26.67%, 6.67%).
With the above example, the cost of path 3 is 4 times the cost of path 2 (20 vs. 5), so path 2 will handle 4 times as much traffic (26.67% vs. 6.67%).
Is that what you want ?
>> so this sums it down: what I am having problem in figuring out is how to actually perform load balancing in such a way that greater weightage is given to nodes with minimum cost AND less weightage is given to nodes with maximum cost.
Unless I'm misunderstanding you, you can just take the inverse of the cost. So, if between a child and the root, there are 3 paths with costs 2, 5 and 20 respectively, then the weights would be 1/2 (= 10/20), 1/5 (= 4/20) and 1/20 respectively, or "normalized" 10/15, 4/15 and 1/15 (in percentages : 66.67%, 26.67%, 6.67%).
With the above example, the cost of path 3 is 4 times the cost of path 2 (20 vs. 5), so path 2 will handle 4 times as much traffic (26.67% vs. 6.67%).
Is that what you want ?
Accepted Solution
20080236-EE-VQP-29 / EE_QW_2_20070628
